Problem D
Gagnaleki

A hacker broke into Forritun.is and leaked several gigabytes of data onto the wider internet, including registration info for contestants of Forritunarkeppni Framhaldsskólanna from all years. In this data there is among other things the username and password from you and other contestants. You find this quite exciting and find this leaked data on the dark web, deciding to try to look into the passwords of the other contestants. But unfortunately the passwords are stored hashed. That is to say, when a contestant logs in for the first time and enters the password, the password is mangled using a hashing function before being entered into the database. Then when a contestant intends to log in the same function is used and the result is compared to the mangled password in the database. If the two are the same, the contestant is logged in, otherwise not.

Clearly the programmers of Forritun.is had safety at the top of their mind since they didn’t store the passwords themselves. That complicates your job, but you don’t give up so easily. On Github you find the following code for the hashing function, implemented in Python:

def heiltala(c):
    if '0' <= c <= '9':
        return int(c)
    return ord(c) - ord('a') + 10

def stafur(c):
    if 0 <= c <= 9:
        return str(c)
    return chr(ord('a') + c - 10)

def leggjaSaman(a, b):
    carry = 0
    s = ''
    for at in range(31, -1, -1):
        carry += heiltala(a[at]) + heiltala(b[at])
        s = stafur(carry % 16) + s
        carry = carry // 16
    return s

def brengla(s, at, u):
    magic = 'b058592efd277ae75f27bd99d1628fbd'
    if at >= len(s):
        return magic

    res = leggjaSaman(brengla(s, at+1, True), brengla(s, at+1, False))
    for i in range(6):
        res = leggjaSaman(res, res)

    cnt = ord(s[at])
    for i in range(cnt):
        res = leggjaSaman(res, magic)

    return res

def taetaLykilord(s):
    return brengla(s, 0, True)


print(taetaLykilord('forrit123'))

You also found the code in the following languages: C++, C#, Java, JavaScript and Ruby.

You had also collected the hashed passwords – all $2\, 500$ of them – in a file you can reach at here, containing one hashed password per line.

With this info on how the hashing function works, you want to try to break as many of the hashed passwords as possible. A hashed password is considered broken when you find some string that gives the same result if you put it through the hashing function. You can use any method you like to break the hashed passwords, including looking up English wordlists on line or change the hashing function to make it faster (as long as it gives the same results).

Input

The program will be run exactly once and the input will be exactly the same as in the file above. On the first line is the number of hashed passwords, which is always $2\, 500$. Then there are $2\, 500$ hashed passwords, one per line.

Output

For each hashed password in the input that you manage to break, print a single line of the format “hashed password:password”, where password is a string giving the result hashed password when put through the hashing function.

Scoring

You get $0.04$ points for each broken password. If the total number of points is not an integer, it is rounded up to the next integer. You also get the following info on the original passwords, before they were hashed:

• 20% of passwords only contain digits and are of length at most $4$.

• 20% of passwords are English words.

• 20% of passwords only contain lower case English letters and are of length at most $5$.

• 20% of passwords are English words with numbers tacked onto the end.

• 20% of passwords consist of up to $15$ English letters, numbers and symbols.

Example

If your solution prints the following it gets $0.2$ points, which is then rounded to $1$ point.

73f5bcbc047219f8ce6fa72e7910b82d:1234
109de74e2dc5851b9e4dc32f40a34eda:benni
c5e0062df0ca99faa2d710c058b3f130:password
3c50164525d099e1b909b3e4b3675a67:sexy1000
053e0ff2244d8f9f1633c0b4f7223e79:mN9`C6ZjGa@!$/L