407427: GYM102788 E Black Box

In the course of decoding flight recorders, an error was discovered in the microcode of one of the controllers that resulted in distortion of the data recorded. According to the results of the investigation, instead of recording $$$n$$$-digit binary numbers ($$$x_1x_2x_3...x_n$$$), the device recorded $$$n$$$-digit results of multiple summing of the initial value with a simultaneous shift to the left ($$$x_1x_2x_3...x_n + x_2x_3...x_n0 + x_3...x_n00 + ... + x_n00...0$$$).

As the capacity of the register where intermediate data are stored equals to $$$n$$$ bits, most significant bits resulting from shifts and summing were discarded. For example, initial number $$$0101$$$ would be transformed into $$$1011$$$:

Moreover, the result of summing was recorded in the order from the least significant bit to the most significant one (i.e., the least significant bit on the left and the most significant, on the right), so the number from the example above would be eventually transformed into $$$1101$$$.

Write a program that will restore the initial number from the encoded one and print the result in the order from the least significant bits to the most significant one.

The first line of the input file contains a value of $$$n$$$ ($$$1 \le n \le 2^{1000000}$$$) – how many bits there are in the given number. The second line contains the summing result – a binary $$$n$$$-bit number recorded starting from the least significant bit.

The output file must contain a single line with the initial $$$n$$$-bit number recorded starting from the least significant bit.

4
1101

1010