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.