# Pwning Passwords [tag:code-golf]

Alice decided to improve the security of her website by [sending first five characters of an SHA-1 hash](https://blog.cloudflare.com/validating-leaked-passwords-with-k-anonymity/) to Bob's Leaked Password Detection Service. However, she made two mistakes that let Eve decode the passwords: sending passwords over HTTP and checking the password after each character of a password is typed. Eve asked you for help in decoding the passwords, however she cannot really program, so needs your help in implementing password cracking algorithm as a computer program or function.

Eve eavesdropped the requests for following hashes from Alice.


```
516B9
379FC
19C2A
9D4E1
08506
F808E
A7F93
5BAA6
```

How could you decode this password? Well, you can brute-force all lowercase letters. In this case the only letter whose hash starts with `516B9` is `p`. The hash of letter `p` is <code><b>516B9</b>783FCA517EECBD1D064DA2D165310B19759</code>.

Knowing that the password starts with `p`, you can brute-force the second character. In this case, the only possible character is `a`. The hash of `pa` is <code><b>379FC</b>0D5299A71AC0F171FBB5AFB262829B4E765</code>

You can continue to brute-force letters one by one to figure out the password was `password` (<code><b>5BAA6</b>1E4C9B93F3F0682250B6CF8331B7EE68FD8</code>). Well, that was simple.

Not all passwords are that simple however. Consider the following requests:

```
4DC7C
A84FD
467D7
BD79D
12D83
```

First three characters of this password are simple: `rxr` (<code><b>467D7</b>856C648A79A096D339A2CE5FC929658967D</code>).

With the fourth character it gets more complicated. BD79D matches for `rxrf` (<code><b>BD79D</b>EC8435B8BA509A25F419F31CC2ACDE2FF0A</code>) and `rxrp` (<code><b>BD79D</b>C20901B11468F8369B5B0D15894F3D96A5E</code>). There is an ambiguity, but as it turns out, it can be resolved by trying both ways. If you assume the password starts with `rxrp` there is no valid letters to continue with. However, if you assume the password starts with `rxrf`, then it's possible to append `a`, resulting in `rxrfa` (<code><b>12D83</b>D3A429CD7D64E9A532C05C2C00C35032A94</code>), which is a valid solution.

All **passwords will be composed entirely out of lowercase letters**. You can assume all inputs have a solution and there are no inputs that could possibly resolve to multiple passwords (for instance `["4DC7C", "A84FD", "467D7", "BD79D"]` is an invalid input because it can match both `"rxrf"` and `"rxrp`").

There are no case requirements on the input. Your program is allowed to assume the input is lowercase. Your program is allowed to assume the input is uppercase.

The program must not take longer to execute than 24 hours for a 25 characters long password.

It is allowed to use external libraries or language built-in functions for computation of SHA-1 hash.

#Example Input and Output

This is a JSON.

```json
[
 {
 "input": [
 "516B9",
 "379FC",
 "19C2A",
 "9D4E1",
 "08506",
 "F808E",
 "A7F93",
 "5BAA6"
 ],
 "output": "password"
 },
 {
 "input": [
 "07C34",
 "593B7",
 "0262F",
 "CED65",
 "23612",
 "4EF76",
 "B7A87"
 ],
 "output": "letmein"
 },
 {
 "input": [
 "84A51",
 "87DDA",
 "83F67",
 "E6FB0",
 "5157D",
 "82CD7",
 "6F655",
 "43426"
 ],
 "output": "codegolf"
 },
 {
 "input": [
 "7A81A",
 "DB3D4",
 "FE05B",
 "E7280",
 "32726",
 "30AE9",
 "2C61A",
 "A9E46",
 "15D98",
 "F780A",
 "3E949",
 "F4BF2",
 "6A5C4",
 "C4554",
 "FA2EA",
 "48A40",
 "5DD7F",
 "5284E",
 "C0B8D",
 "20D59",
 "9184C",
 "32AD9"
 ],
 "output": "onetwothreefourfivesix"
 },
 {
 "input": [
 "84A51",
 "87DDA",
 "26CA7",
 "9D925",
 "08A23",
 "BE075",
 "3179A",
 "5D904",
 "54C70",
 "47790",
 "5D3B5",
 "0E4CE",
 "004C7",
 "EC8A8",
 "131A6",
 "7F47F",
 "41BC6",
 "FCF07",
 "D62BD",
 "DD14F",
 "6A141",
 "EE184",
 "595F8",
 "9D303",
 "BFD36"
 ],
 "output": "correcthorsebatterystaple"
 },
 {
 "input": [],
 "output": ""
 },
 {
 "input": [
 "4DC7C",
 "A84FD",
 "467D7",
 "BD79D",
 "12D83"
 ],
 "output": "rxrfa"
 },
 {
 "input": [
 "4DC7C",
 "A84FD",
 "467D7",
 "BD79D",
 "7B743"
 ],
 "output": "rxrpa"
 }
]
```