Тест
Артем проходит учебный тест в электронной системе. Вопрос теста содержит n утверждений, некоторые из которых являются истинными и их необходимо отметить флажками. Поставив некоторые из флажков, можно проверить ответ на правильность. Ответ на вопрос считается правильным, если все истинные утверждения отмечены флажками, а все ложные — нет.
Думать Артему лень, поэтому он решил просто перебрать все варианты расстановки флажков. Для этого он составляет список всех 2^n вариантов их расстановки. В списке каждый вариант расстановки флажков должен присутствовать ровно один раз.
Интуитивно ему кажется, что истинных утверждений много, поэтому варианты расстановки он хочет перебирать в порядке уменьшения количества установленных флажков. Помимо этого, Артем очень ленив и хочет, чтобы для двух подряд идущих вариантов количество позиций, в которых они различаются, не превосходило двух. Помогите Артему.
Входные данные
В первой строке содержится целое число n (1 ≤ n ≤ 16).
Выходные данные
Выведите 2^n строк. В i-й строке выведите n символов 0 или 1 — состояние каждого из флажков для i-го варианта ответа, 1 для установленного флажка и 0 для неустановленного. Количество единиц в вариантах должно неубывать. Количество позиций, в которых различаются две соседние строки, не должно превосходить двух.