Test
Artem is taking a practice test using an electronic system. The test consists of n statements, some of which are true and need to be marked with checkboxes. After selecting some checkboxes, he can verify if his answer is correct. An answer is considered correct if all true statements are checked, and all false ones are not.
Artem, feeling too lazy to think, decides to try every possible combination of checkbox selections. To do this, he creates a list of all 2^n possible combinations. Each combination of checkbox selections must appear exactly once in this list.
He suspects that many statements are true, so he wants to test the combinations in order of decreasing number of checked boxes. Additionally, Artem wants to minimize his effort, so he prefers that the number of positions where two consecutive combinations differ is no more than two. Help Artem achieve this.
Input
The first line contains an integer n (1 ≤ n ≤ 16).
Output
Output 2^n lines. On the i-th line, output n characters, either 0 or 1, representing the state of each checkbox for the i-th answer option. Use 1 for a checked box and 0 for an unchecked box. The number of ones in the options should not decrease. The number of positions where two consecutive lines differ should not exceed 2.