Недавно Вадим написал свою игру, которую он назвал «Сavalry Battle Advanced». Эта игра отдалённо напоминает шахматы, но отличается некоторыми важными моментами:

Чтобы все игроки не заполняли всё доступное поле 3 × N конями, Вадим закодировал секретный бонус. Чтобы подробнее разобраться в нём, представим себе граф, в котором каждый поставленный конь является вершиной, а если пара коней бьют друг друга, то между соответствующими вершинами в графе стоит ребро. Бонус добавляется только в том случае, если этот граф является деревом (то есть этот граф связный и без циклов).

Предельно понятно, что все профессиональные игроки в «Сavalry Battle Advanced» хотят как получить этот секретный бонус, так и расставить при этом наибольшее возможное количество коней в обозначенное поле. Побудьте в роли этих игроков и найдите подобную расстановку.

В единственной строке вводится целое число N — размер поля по горизонтали (1 ≤ N ≤ 10⁵).

Выведите расстановку в следующем формате: 3 строки по N чисел 0 или 1 — 0, если клетка пустая, и 1, если в клетке стоит конь. Таким образом, у вас получится таблица размера 3 × N. Все кони должны образовывать дерево описанным в условии образом.

Если есть несколько подходящих расстановок с наибольшим количеством коней, выведите любую из них.