G. Self-Synchronizing Code
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is a double-run problem.

In a physics lab, students developed a device that allows transmitting text messages consisting of lowercase Latin letters using a laser. Before sending, a message is converted into binary code and then transmitted sequentially, bit by bit.

However, during testing of the device, a problem was discovered. It turned out that if four identical bits in a row appear during transmission (that is, «0000» or «1111»), synchronization is lost on the receiving side. Therefore, it is necessary to come up with an encoding method for which this situation is impossible. The developers also want the number of bits in the encoded message to exceed the length of the original message by no more than six times.

Develop some encoding and decoding method satisfying these requirements.

Input

The first line of the input contains an integer $$$t$$$, equal to 1 or 2.

If $$$t=1$$$, then the second input line contains the message that must be encoded. It consists of lowercase Latin letters and has length from 1 to 10000 characters.

If $$$t=2$$$, then the second input line contains a message previously encoded by your program, which must be decoded.

Output

Print one line — the encoded or decoded message.

Example
Input
1
aba
Output
100101101101100101
Input
2
100101101101100101
Output
aba