Грејов кôд реда \(n\) подразумева ређање свих \(n\)-тоцифрених бинарних записа тако да се свака два суседна записа разликују тачно у једном биту (при чему ово важи и за први и последњи запис, тако да се може сматрати да су сви записи поређани у круг).

Грејов кôд дужине \(0\) садржи само један елемент и то празну ниску. Грејов кôд дужине \(n+1\) се може добити од кода дужине \(n\) тако што се испред сваког броја у коду дужине \(n\) допише цифра \(0\), затим се редослед елемената у коду дужине \(n\) обрне и на сваком броју се на почетак допише цифра \(1\) и два тако добијена низа бројева се споје. Нпр. Грејов кôд реда \(2\) је

00
01
11
10

На основу претходног поступка добијамо Грејов кôд реда \(3\).

0 00  |                 k
0 01  |                 0:  000
0 11  |                 1:  001
0 10  v                 2:  011
             tj.        3:  010
1 10  ^                 4:  110
1 11  |                 5:  111
1 01  |                 6:  101
1 00  |                 7:  100

Напиши програм који за дату дужину кода \(n\) исписује комплетан Грејов код дужине \(n\).

Улаз

Са стандардног улаза се учитава дужина кода \(n\) (\(1 \leq n \leq 14\)).

Излаз

На стандардни излаз исписати тражени код.

Пример 1

Улаз

3

Излаз

000
001
011
010
110
111
101
100

Пример 2

Улаз

4

Излаз

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