시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 64 MB 0 0 0 0.000%

문제

Mali Nikola je nepresušnim nizom pitanja upravo natjerao svoju profesoricu matematike u ludilo. Posve iznervirana, ona za kaznu zadaje cijelom razredu sljedeći zadatak:

"Promotrimo sve različite NIZOVE (eto ti sad niza, Nikola!) koji se sastoje od N binarnih znamenki (tih nizova ima 2N ). Nañite permutaciju nizova u kojoj je udaljenost svaka dva uzastopna niza jednaka jedan".

Učiteljica je još napomenula da se udaljenost izmeñu dva binarna niza definira kao broj pozicija na kojima se odgovarajući elementi nizova razlikuju. Na primjer:

Udaljenost( 111, 000 ) = 3                    /nizovi se razlikuju na prvoj, drugoj i trećoj poziciji/
Udaljenost( 111100, 101010 ) = 3        /nizovi se razlikuju na drugoj, četvrtoj i petoj poziciji/
Udaljenost( 110011, 110011 ) = 0

Pomozite Nikoli da pronañe traženu permutaciju. 

입력

U prvom i jedinom retku nalazi se prirodni broj N ≤ 16, duljina binarnih nizova. 

출력

Ispišite traženu permutaciju tako da ispišete 2N različitih binarnih nizova, svaki u svojoj liniji. Svaki niz se mora sastojati od točno N znamenki '0' ili '1'. Udaljenost izmeñu svaka dva susjedna niza mora biti točno jedan.

Možete pretpostaviti da će uvijek postojati barem jedno rješenje.

예제 입력 1

1

예제 출력 1

0
1

예제 입력 2

2

예제 출력 2

00
01
11
10

예제 입력 3

3

예제 출력 3

000
001
011
111
101
100
110
010