cifru

Copiii solarieni se joacă adesea trimiţându-şi mesaje codificate. Pentru codificare ei folosesc un cifru bazat pe o permutare $p$ a literelor alfabetului solarian şi un număr natural $d$.
Alfabetul solarian conţine $m$ litere foarte complicate, aşa că noi le vom reprezenta prin numere de la $1$ la $m$.
Dat fiind un mesaj în limbaj solarian, reprezentat de noi ca o succesiune de $n$ numere cuprinse între $1$ şi $m$, $c_1 \ c_2 \dots c_n$, codificarea mesajului se realizează astfel: se înlocuieşte fiecare literă $c_i$ cu $p(c_i)$, apoi şirul obţinut $p(c_1) \ p(c_2) \dots p(c_n)$ se roteşte spre dreapta, făcând o permutare circulară cu $d$ poziţii rezultând şirul $p(c_{n-d+1}) \dots p(c_{n-1}) \ p(c_n) \ p(c_1) \ p(c_2) \dots p(c_{n-d})$.
De exemplu, pentru mesajul $2 \ 1 \ 3 \ 3 \ 2 \ 1$, permutarea $p = (3 \ 1 \ 2)$ (adică $p(1)=3$, $p(2)=1$, $p(3)=2$) şi $d=2$. Aplicând permutarea $p$ vom obţine şirul $1 \ 3 \ 2 \ 2 \ 1 \ 3$, apoi rotind spre dreapta şirul cu două poziţii obţinem codificarea $1 \ 3 \ 1 \ 3 \ 2 \ 2$.

Cerinţă

Date fiind un mesaj necodificat şi codificarea sa, determinaţi cifrul folosit (permutarea $p$ şi numărul $d$).

Date de intrare

Fişierul de intrare cifru.in conţine pe prima linie numele naturale $n$ şi $m$, separate prin spaţiu, reprezentând lungimea mesajului şi respectiv numărul de litere din alfabetul solarian. Pe cea de a doua linie este scris mesajul necodificat ca o succesiune de $n$ numere cuprinse între $1$ şi $m$ separate prin câte un spaţiu. Pe cea de a treia linie este scris mesajul codificat ca o succesiune de n numere cuprinse între $1$ şi $m$ separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire cifru.out va conţine pe prima linie numărul natural $d$, reprezentând numărul de poziţii cu care s-a realizat permutarea circulară spre dreapta. Dacă pentru $d$ există mai multe posibilităţi se va alege valoarea minimă. Pe următoarea linie este descrisă permutarea $p$. Mai exact se vor scrie valorile $p(1)$, $p(2)$, $\dots$, $p(m)$ separate prin câte un spaţiu.

Restricții și precizări

• $n \leq 100 \ 000$
• $m \leq 9 \ 999$
• Mesajul conţine fiecare număr natural din intervalul $[1, m]$ cel puţin o dată.
• Pentru teste cu $m \leq 5$ se acordă $40$ de puncte din care $20$ pentru teste şi cu $n \leq 2 \ 000$.

Exemplu

cifru.in

6 3
2 1 3 3 2 1
1 3 1 3 2 2

cifru.out

2
3 1 2