22120번 - Тест 스페셜 저지다국어

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

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

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

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

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