eolymp
bolt
Try our new interface for solving problems

Тест

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Артем проходит учебный тест в электронной системе. Вопрос теста содержит n утверждений, некоторые из которых являются истинными и их необходимо отметить флажками. Поставив некоторые из флажков, можно проверить ответ на правильность. Ответ на вопрос считается правильным, если все истинные утверждения отмечены флажками, а все ложные — нет.

Думать Артему лень, поэтому он решил просто перебрать все варианты расстановки флажков. Для этого он составляет список всех 2^n вариантов их расстановки. В списке каждый вариант расстановки флажков должен присутствовать ровно один раз.

Интуитивно ему кажется, что истинных утверждений много, поэтому варианты расстановки он хочет перебирать в порядке уменьшения количества установленных флажков. Помимо этого, Артем очень ленив и хочет, чтобы для двух подряд идущих вариантов количество позиций, в которых они различаются, не превосходило двух. Помогите Артему.

Giriş verilənləri

В первой строке содержится целое число n (1n16).

Çıxış verilənləri

Выведите 2^n строк. В i-й строке выведите n символов 0 или 1 — состояние каждого из флажков для i-го варианта ответа, 1 для установленного флажка и 0 для неустановленного. Количество единиц в вариантах должно неубывать. Количество позиций, в которых различаются две соседние строки, не должно превосходить двух.

Nümunə

Giriş verilənləri #1
2
Çıxış verilənləri #1
11
10
01
00