eolymp
bolt
Try our new interface for solving problems
Məsələlər

Взлом шифра

Взлом шифра

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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

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

Более формально: предположим, что Алан нажал на кнопки k раз. Пусть a_i (1ik) — номер кнопки, которую Алан нажал i по счету, а b_1, b_2, ..., b_n — секретная перестановка. Тогда замок открывается, если существует такое число x (1xk − n + 1), что b_1 = a_x, b_2 = a_{x+1}, ..., b_n = a_{x+n−1}.

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

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
2
Çıxış verilənləri #1
3
1 2 1