Şifrənin sındırılması
Aylan şifrələri və kod kilidlərini açmağı sevir. Bu dəfə ona qeyri-adi dərəcədə çətin bir kilid düşüb və Aylan bu kilidin açarını tapa bilmədi. Buna görə də, o, bütün mümkün kombinasiyaları yoxlamağa qərar verdi ki, açarı tapsın.
Kilid n düymədən ibarətdir və bu düymələr 1-dən n-ə qədər tam ədədlərlə nömrələnib. Kilid yalnız bəzi ardıcıl n düymə basıldıqda müəyyən bir gizli permutasiyanı təşkil etdikdə açılır. Kilidin düymələrini ardıcıl basmaq lazımdır; eyni anda iki və ya daha çox düyməni basmaq olmaz.
Daha dəqiq desək: tutaq ki, Aylan k dəfə düymələri basdı. Qoy a_i (1 ≤ i ≤ k) Aylanın i-ci dəfə basdığı düymənin nömrəsi olsun və b_1, b_2, ..., b_n gizli permutasiya olsun. Onda kilid açılır, əgər elə bir x (1 ≤ x ≤ k − n + 1) ədədi varsa ki, b_1 = a_x, b_2 = a_{x+1}, ..., b_n = a_{x+n−1}.
Aylan elə bir universal düymə basma ardıcıllığı düşünmək istəyir ki, bu ardıcıllıqla düymələr basıldıqda kilid hər hansı bir gizli permutasiya üçün açılsın. Həmçinin, Aylan istəyir ki, bu ardıcıllıq çox uzun olmasın, yəni, onun uzunluğu 2n!-dən çox olmasın, burada n! = 1 · 2 · ... · n. Məsələn, n = 3 üçün ardıcıllığın uzunluğu 12-dən çox olmamalıdır.
Aylana belə bir ardıcıllığı tapmaqda kömək edin.
Giriş verilənləri
Giriş faylının yeganə sətrində n (1 ≤ n ≤ 9) tam ədədi verilir — kod kilidindəki düymələrin sayı.
Çıxış verilənləri
Çıxış faylının birinci sətrində k (0 ≤ k ≤ 2n!) — universal ardıcıllığın uzunluğunu yazın. İkinci sətrdə k tam ədəd a_i, boşluqlarla ayrılmış (1 ≤ a_i ≤ n) — düymələrin basılma sırasını yazın. Diqqət yetirin ki, uzunluğu 2n!-dən çox olmayan istənilən ardıcıllığı çıxış edə bilərsiniz, uzunluğu minimallaşdırmaq lazım deyil. Hər hansı n üçün belə bir ardıcıllığın mövcudluğu təmin edilir.