Practice Cryptography with the exercise "The Empire Enigma"

Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

Cryptography

Statement

Goal

Write a decoder to allow the rebellion to decipher the Empire's secret messages.

The rebelllion figured out that characters in the original message are encoded by XOR'ing them with a stream of random numbers:

- The Empire uses ASCII codes for their original message.

- First character of each original message is always @.

- Each message is encoded with a different Seed for the Random Number Generator (RNG).

- The first Offset numbers from the RNG are discarded before encoding.

- Each undiscarded random number from the RNG is then XOR'ed with the ASCII code of each character, truncated to the lowest 8 bits. The resulting number then becomes part of the encoded message.

- The RNG used is:
R(n+1) = (7562100 * R(n) + 907598307) mod 7140
where R(0) = Seed, R(1) is the first number from the RNG, R(2) is the second, etc.

The Empire believes that security is guaranteed by using large seeds (0 < Seed < 2^63) and the large offsets ( 0 ≤ Offset < 2^63) which should prevent any brute force attack. Apparently you have a better way to work around the security than simple brute force!

Example
The original message @Hello is encoded with Seed = 581980637 and Offset = 10 to obtain the encoded message of 135 155 214 19 183 44.

Input

Line 1: An integer Offset for the random numbers from the RNG to discard before starting XOR'ing.
Line 2: An integer Length for the length of the message including @.
Next Length lines: One integer C in each line for each encoded character of the message.

Output

Line 1: The decoded message excluding the initial @.

Constraints

0 < Seed < 2^63
0 ≤ Offset < 2^63
0 < Length < 256
32 ≤ ASCII code of each character in the original message ≤ 126

Example

Input

Output

Hello

Solve it

A higher resolution is required to access the IDE