Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

B. Good Spotlights
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

In the final of the Tengo-lengo-tengo Football World Cup, the stadium light show is the highlight of halftime while several artists perform on stage. Each spotlight configuration is represented by a binary number with exactly $$$3$$$ bits: bit $$$0$$$ means a light is off, and bit $$$1$$$ means a light is on.

To make the halftime show look smooth, the organizers want the lights to change calmly. Therefore, from one configuration to the next, exactly one spotlight must change state.

You are given an initial configuration $$$X_0$$$. Your task is to produce a sequence that starts at $$$X_0$$$, visits all $$$8$$$ configurations of $$$3$$$ bits exactly once, and then returns to $$$X_0$$$.

Input

The input contains a single line with a string $$$X_0$$$ of exactly $$$3$$$ characters. Each character of $$$X_0$$$ is either 0 or 1.

Output

Print $$$9$$$ binary strings of exactly $$$3$$$ bits.

The first and the last string must be equal to $$$X_0$$$. Among the first $$$8$$$ strings, each of the $$$8$$$ possible configurations must appear exactly once. Also, any two consecutive strings in your output must differ in exactly one bit.

If there is more than one valid answer, print any of them.

Example
Input
010
Output
010
110
111
101
100
000
001
011
010
Note