Xiaoqiang and Amoeba are good friends. They grew up together and spent a carefree childhood. When they were young, they loved playing games together, such as flipping coins. They would flip coins together and then guess whether the coin landed heads or tails. Xiaoqiang gradually gained the upper hand in the process of guessing, as his accuracy was always slightly higher than Amoeba's.

To figure out why Xiaoqiang always won, Amoeba recorded all their coin-tossing results in a file. This file is a long binary string of 0s and 1s, where 1 represents heads and 0 represents tails. To prevent Xiaoqiang from discovering his actions, Amoeba encrypted this file using an algorithm he designed himself.

This algorithm has a parameter $N$, two keys $K_1$ and $K_2$, and a register $X$. The algorithm is as follows:

1. $X_0 = K_1$
2. Read each bit $I_p$ of the input sequentially, and perform the following calculations for each:
3. $T_p = w(f(X_p) \text{ and } K_2)$
4. $O_p = I_p \text{ xor } T_p$
5. $X_{p+1} = (2X_p + O_p) \pmod{2^N}$
6. Output $O_p$

Where: $f(x) = (1994x^5 + 11x^4 + 4x^3 + 1995x^2 + 9x + 24) \pmod{2^N}$ and represents the bitwise AND operation (the & operator in C/C++), xor represents the bitwise XOR operation (the ^ operator in C/C++), and mod represents the modulo operation (the % operator in C/C++).

$w(x)$ represents the parity of the number of 1s in the binary representation of $x$. If $x$ contains an odd number of 1s, then $w(x) = 1$; if $x$ contains an even number of 1s, then $w(x) = 0$. For example, $w(13) = w(1101_2) = 1$, and $w(12) = w(1100_2) = 0$.

Amoeba found that this algorithm had a good encryption effect.

Now, Xiaoqiang and Amoeba have both grown up. They entered different universities and have rarely seen each other since. Over time, Amoeba forgot the key used to encrypt the file, remembering only that $K_1$ and $K_2$ represented a small secret between them. He knows that $N$ is not very large, and that $K_1$ and $K_2$ are both 64-bit binary numbers not exceeding $2^N$. He really wants to recover this set of keys from the ciphertext. However, having studied algebra and probability theory, he knows this is almost impossible. So, he went to find Xiaoqiang.

Xiaoqiang smiled mysteriously after hearing this. "Do you know why I can guess more accurately than you?" "Why?" "Because this coin is not fair; the probability of it landing tails is $\frac{1}{2} + b$, which is higher than heads."

Amoeba immediately saw hope for recovering the key. "However, given enough ciphertext, I can only recover $K_2$." "Well, that is also good enough."

Input

The input file is crypto.in. Its length is 1048576 bytes, representing an 8388608-bit binary number. The most significant bit comes first, and the least significant bit comes last. For example, 011000010110110101100010 recorded becomes the three bytes "amb". This file represents the content of the encrypted file.

Output

The output file is crypto.out. It consists of a single line of 64 0s or 1s, representing the binary representation of $K_2$.

Examples

Since the input and output files are relatively large, you will be provided with a data generator located at crypto/cryptogen.py. To use it, first enter the terminal and run the following command to enter the problem folder:

cd crypto

Then run the following command:

python cryptogen.py N b

Where $N$ and $b$ are the parameters of the algorithm, for example:

python cryptogen.py 50 0.3

After waiting for a while, you will obtain the input file crypto.in and the standard output file crypto.ans. The plaintext and other information will be saved in crypto.log for your debugging convenience.

Note that the data generator is random; inputting the same parameters will almost always result in different outputs. Please keep the sample data generated each time.

Implementation Details

In C/C++, you can use the fread function to read/write binary files. You can view the specific usage by running the following command in the terminal:

man fread

Below is an example:

#include <stdio.h>
int main()
{
    FILE *fin=fopen("crypto.in","rb");
    static unsigned char data[1<<20];
    fread(data,1,1<<20,fin);
    return 0;
}

For Pascal contestants, the following example might be helpful:

program crypto;
var
    MyFile: file;
    Data: array [0..999999] of Byte;
begin
    Assign(MyFile, 'crypto.in');
    Reset(MyFile, 1);
    BlockRead(MyFile, Data, SizeOf(Data));
    Close(MyFile);
end.

Constraints

The parameters for the 10 test cases used for evaluation are as follows:

Note

If four events each occur with a probability of 0.62, then the probability that an odd number of events occur is approximately 0.49834112. To distinguish with high confidence whether the probability of a coin landing heads is $\frac{1}{2}$ or $\frac{1}{2} - d$, the number of coin flips required is proportional to $d^{-2}$.