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