Тест#5762

Тест

2 секунди

256 мегабайтів

Середня

Артем проходить навчальний тест у електронній системі. Питання тесту містить $n$ тверджень, деякі з яких є істинними і їх необхідно відмітити прапорцями. Поставивши деякі з прапорців, можна перевірити відповідь на правильність. Відповідь на питання вважається правильною, якщо всі істинні твердження відмічені прапорцями, а всі хибні — ні.

Думати Артему ліньки, тому він вирішив просто перебрати усі варіанти розстановки прапорців. Для цього він складає список усіх $2^{n}$ 2^n варіантів їх розстановки. У списку кожен варіант розстановки прапорців повинен бути присутнім рівно один раз.

Інтуїтивно йому здається, що істинних тверджень багато, тому варіанти розстановки він хоче перебирати у порядку зменшення кількості встановлених прапорців. Крім цього, Артем дуже лінивий і хоче, щоб для двох підряд ідучих варіантів кількість позицій, у яких вони відрізняються, не перевищувала двох. Допоможіть Артему.

Вхідні дані

У першому рядку міститься ціле число $n$ ( $1 \leq n \leq 16$ 1 \leq n \leq 16).

Вихідні дані

Виведіть $2^{n}$ 2^n рядків. У $i$ -му рядку виведіть $n$ символів $0$ або $1$ — стан кожного з прапорців для $i$ -го варіанту відповіді, $1$ для встановленого прапорця і $0$ для невстановленого. Кількість одиниць у варіантах повинна не зростати. Кількість позицій, у яких відрізняються два сусідні рядки, не повинна перевищувати $2$ .

Приклади

Приклад 1