Cho số nguyên N ~(2 \le N \le 12)~.

Đặt ~s = 2^N~. Tìm cách xếp các số từ 0 đến ~s-1~ lên vòng tròn sao cho cứ 2 số đứng cạnh nhau, thì biểu diễn nhị phân của nó có ít nhất ~n/2~ bit khác nhau (phép chia nguyên, ví dụ ~n=3~ thì cần 1 bit khác nhau).

Input

Gồm 1 dòng duy nhất chứa số nguyên N

Output

Gồm ~s~ dòng, mỗi dòng in ra 1 dãy nhị phân gồm đúng ~N~ bit thỏa mãn đề bài

Sample Input 1

2

Sample Output 1

00
01
10
11

Sample Input 2

3

Sample Output 2

000
011
010
110
100
101
111
001