Content Scramble with LFSR Recovery

This is a submission problem. You are given a partial keystream generated from a simplified Content Scramble System (CSS) based on two linear feedback shift registers (LFSRs). The secret key k is a 42-bit binary string k₁, k₂, ..., k₄₂.

The encryption works as follows:

• The keystream T(k) of n bytes is generated by first initializing two LFSRs with parts of the key, then repeatedly generating a byte by combining one step from each LFSR.

LFSR Details:

• LFSR17: state of 17 bits, feedback positions: {1, 15}, initialized with k₁ ... k₁₇.
• LFSR25: state of 25 bits, feedback positions: {1, 4, 5, 13}, initialized with k₁₈ ... k₄₂.

Each LFSR performs the following in one cycle: output the XOR of bits in the feedback set and then shift all bits with the new bit appended at the end. A step is 8 cycles which produce 8 bits. The 8 bits obtained in one step (in order i₁, i₂, …, i₈) are then arranged (with bit reversal) into a byte:

\( (\overline{i_8 i_7 i_6 i_5 i_4 i_3 i_2 i_1})_2 \)

The keystream is generated as follows:

1. Initialize LFSR17 and LFSR25 using k.
2. Set a carry c = 0.
3. Repeat n times:
1. Obtain byte x from LFSR17 executing one step.
2. Obtain byte y from LFSR25 executing one step.
3. Compute \( z = x + y + c \).
4. Update \( c = \lfloor z / 256 \rfloor \) and \( z = z \bmod 256 \).
5. Append byte z to the keystream.

Given a partial keystream (the first n bytes of T(k)), your task is to output a possible key k (a 42-character string consisting of 0's and 1's) that can generate a keystream matching the given partial sequence.

Note: The input file can be downloaded as an attachment. For this problem, you may assume that the test cases are designed so that the partial keystream consists solely of zero bytes. In such cases, the key consisting of 42 zeros is a valid solution.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 10⁵), representing the number of bytes in the partial keystream.

The second line contains n integers (each in the range 0 to 255) separated by spaces, which represent the partial keystream bytes.

Note: In the given test cases, all bytes will be 0.

outputFormat

Output a single line containing a 42-character string of 0's and 1's representing a possible key k that generates a keystream matching the provided partial keystream.

Hint: If all the provided keystream bytes are 0, then the key "000000000000000000000000000000000000000000" is a valid answer.

sample

3
0 0 0

000000000000000000000000000000000000000000