Problem E
Chalmers Coin

The industrial engineering and management division at Chalmers have recently invented something they think will revolutionize money. They have invented a brand new cryptocurrency called the Chalmers Coin (CC)! To mine a block of CC you need to find a sufficiently small value of $\texttt{hash}(x \, .\, k)$ where $\, .\, $ is bit-concatenation, $x$ is a given $28$-bit number, $k$ is a $36$-bit number you can choose freely and $\texttt{hash}$ is the function defined below. A different way of writing the same thing would be $\texttt{hash}(2^{36} x + k)$.

The industrial management students were confident they had the resources and the expertise to create a hash function better than SHA256. One of their genius ideas was to use a $64$-bit input and output to save storage space. The result of their extensive research, the hash function used in CC, is defined by the following python code.

def hash(x):
    # int to list of bits
    def tolist(x):
        return [(x>>i)&1 for i in range(63, -1, -1)]

    # list of bits to int
    def toint(x):
        return sum([x[63-i]<<i for i in range(0, 64)])

    assert 0 <= x < 2**64
    x = tolist(x)
    for i in range(512):
        y = 4*x[i%64] + 2*x[(i+2)%64] + x[(i+10)%64]
        x[i%64] = [1,1,0,0,1,1,0,1][y]
    x = toint(x)
    for i in range(16):
        x += toint(tolist(x)[::-1])
        x ^= 3**40
        if(x >= 2**64): x >>= 1
    assert 0 <= x < 2**64
    return x

You want to get rich by mining this coin. The Chalmers Coin automatically changes its difficulty (how small the hash needs to be). Therefore, you want to write a program which finds a value of $k$ to make the hash as small as possible, the smaller the better.

Input

Input consists of $10$ lines, each describing a block you want to mine. The $i$th line contains the integer $x_ i$. All $x_ i$ are sampled uniformly at random from $[0, 2^{28}-1]$.

Output

Output $10$ integers $k_ i$, one per line.

Scoring

Your program will only be run on one test case (containing $10$ lines). The sample test case is not worth any points. Your final score is the sum of your score for each block, rounded to two decimal places. For each block, your score is $\max (2t_ i, 30t_ i-20)$ where $t_ i = \frac{64-\log _2(h_ i)}{64-\log _2(H_ i)}$, $h_ i$ is the hash you have obtained ($h_ i = \texttt{hash}(2^{36} x_ i + k_ i)$) and $H_ i$ is the optimal hash.

TL;DR: You will get more points the smaller hashes you get.

Explanation of sample

For the first block, the sample output gets the hash $h_1 = \texttt{hash}(2^{36} \cdot 111131462 + 50363195222) = \texttt{hash}(7636895967909863254) = 15659998746091827$. An optimal answer for the first block would have been $1090594820$, corresponding to the hash $H_1 = 602833507760528$. This gives $t_1 = \frac{64-\log _2(h_1)}{64-\log _2(H_1)} \approx 0.68465$ and a score for the first block of approximately $\max (2 \cdot 0.68465, 30 \cdot 0.68465-20) = 1.3693$.

111131462
229052375
257596593
38597773
23809983
258400715
233947578
110845532
114293771
9972238

50363195222
42418249845
33054711477
17285915666
56435782313
45159025508
17257367058
25150682838
27482402594
16944532377