Артем проходить навчальний тест у електронній системі. Питання тесту містить \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} для не встановленого. Кількість одиниць у варіантах повинна не спадати. Кількість позицій, у яких відрізняються два сусідні рядки, не повинна перевищувати \textbf{2}.