Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 2597
Yellow Code

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

Inspired by Gray code, professor John Yellow has invented his own code. Unlike in Gray code, in Yellow code the adjacent words have many different bits.

More precisely, for s = 2n we call the permutation a1, a2, ... , as of all n-bit binary words the Yellow code if for all 1 <= k < s words ak and ak+1 have at least [n/2] different bits and a1 and as also have at least [n/2] different bits. ([n/2] indicates the largest integer that does not exceed n/2.)

Given n you have to find the n-bit Yellow code or detect that there is none.

Input

In each line of input file there is an integral number n (2 <= n <= 12). A line with n = 0 indicates the end of input, which should not be proceeded.

Output

For each test case, output 2n n-bit binary vectors in the order they appear in some n-bit Yellow code, one on a line. If there is no n-bit Yellow code, output "none" on the first line.

Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.

Sample Input

```4
2
0
```

Sample Output

```0000
1010
0101
1111
0010
1001
0111
1100
0001
1011
0100
1110
0011
1000
0110
1101

00
10
01
11
```

Author: Andrew Stankevich
Source: Andrew Stankevich's Contest #6
Submit    Status