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