Задача A. Взлом шифра

Автор:А. Васильев, В. Аксёнов (Жюри XXI командной олимпиады школьников СПб по информатике)   Ограничение времени:2 сек
Входной файл:cipher.in   Ограничение памяти:256 Мб
Выходной файл:cipher.out  

Условие

Алан любит вскрывать шифры и кодовые замки. На этот раз ему попался необычайно сложный замок, найти ключ к которому Алану не удалось, поэтому он решил перебрать все возможные комбинации, чтобы узнать ключ.

Замок представляет собой n кнопок, пронумерованных целыми числами от 1 до n. Замок открывается только тогда, когда какие-то последовательные n нажатий на кнопки образуют некоторую секретную перестановку. Кнопки замка следует нажимать по очереди, нажать одновременно две или более кнопки нельзя.

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть ai (1 ≤ i ≤ k) — номер кнопки, которую Алан нажал i по счету, а b1, b2, …, bn — секретная перестановка. Тогда замок открывается, если существует такое число x (1 ≤ x ≤ k − n + 1), что b1 = ax, b2 = ax+1, , bn = ax+n1.

Алан хочет придумать такую универсальную последовательность нажатий, что при нажатии кнопок в такой последовательности замок откроется для любой секретной перестановки. Также Алан хочет, чтобы эта последовательность не была слишком длинной, а именно, ее длина не превышала 2 n!, где n! = 1 ⋅ 2 ⋅ … ⋅ n. Например, для n = 3 длина последовательности не должна превышать 12.

Помогите Алану найти такую последовательность.

Формат входного файла

В единственной строке входного файла находится целое число n (1 ≤ n ≤ 9) — количество кнопок на кодовом замке.

Формат выходного файла

В первой строке выходного файла выведите число k (0 ≤ k ≤ 2 n!) — длину универсальной последовательности. Во второй строке выведите k целых чисел ai, разделенных пробелами (1 ≤ ai ≤ n) — порядок, в котором следует нажимать кнопки. Обратите внимание, что достаточно вывести любую последовательность длины не более 2 n!, минимизировать длину не нужно. Гарантируется, что такая последовательность существует для любого n.

Примеры тестов

Входной файл (cipher.in) Выходной файл (cipher.out)
1
2
3
1 2 1
2
3
10
1 2 3 1 3 2 1 3 1 2

0.030s 0.006s 15