== include(page="template/taskheader" task_id="cifru2") ==
Copiii solarieni se joaca adesea trimitandu-si mesaje codificate. Pentru codificare ei folosesc un cifru bazat pe o permutare $p$ a literelor alfabetului solarian si un numar natural $d$.
Alfabetul solarian contine $m$ litere foarte complicate, asa ca noi le vom reprezenta prin numere de la $1$ la $m$.
Dat fiind un mesaj in limbaj solarian, reprezentat de noi ca o succesiune de $n$ numere cuprinse intre $1$ si $m$, $c{~1~}$ $c{~2~}$ ... $c{~n~}$, codificarea mesajului se realizeaza astfel: se inlocuieste fiecare litera $c{~i~}$ cu {$p$}({$c{~i~}$}), apoi sirul obtinut {$p$}({$c{~1~}$}) {$p$}({$c{~2~}$}) ... {$p$}({$c{~n~}$}) se roteste spre dreapta, facand o permutare circulara cu $d$ pozitii rezultand sirul {$p$}({$c{~n-d+1~}$}), ... ,{$p$}({$c{~n-1~}$}), {$p$}({$c{~n~}$}), {$p$}({$c{~1~}$}), {$p$}({$c{~2~}$})... {$p$}({$c{~n-d~}$}).
De exemplu, pentru mesajul $2 1 3 3 2 1$, permutarea {$p$}=({$3 1 2$}) (adica {$p$}({$1$})=3, {$p$}({$2$})=1, {$p$}({$3$})=2) si {$d$}={$2$}. Aplicand permutarea $p$ vom obtine sirul {$1 3 2 2 1 3$}, apoi rotind spre dreapta sirul cu doua poziţii obtinem codificarea {$1 3 1 3 2 2$}.
h2. Cerinta
Date fiind un mesaj necodificat si codificarea sa, determinati cifrul folosit (permutarea p si numarul d).
Poveste si cerinta...
h2. Date de intrare
Fisierul de intrare $cifru.in$ contine pe prima linie numele naturale n si m, separate prin spatiu, reprezentand lungimea mesajului si respectiv numarul de litere din alfabetul solarian. Pe cea de a doua linie este scris mesajul necodificat ca o succesiune de $n$ numere cuprinse intre $1$ si $m$ separate prin cate un spatiu. Pe cea de a treia linie este scris mesajul codificat ca o succesiune de $n$ numere cuprinse intre $1$ si $m$ separate prin cate un spatiu.
...
h2. Date de iesire
Fisierul de iesire $cifru.out$ va contine pe prima linie numarul natural $d$, reprezentand numarul de pozitii cu care s-a realizat permutarea circulara spre dreapta. Daca pentru d exista mai multe posibilitati se va alege valoarea minima. Pe urmatoarea linie este descrisa permutarea p. Mai exact se vor scrie valorile {$p$}({$1$}), {$p$}({$2$}), …, {$p$}({$m$}) separate prin cate un spatiu.
...
h2. Restrictii
* {$ 2 ≤ n ≤ 100 000 $}
* {$ 2 ≤ m ≤ 9999 $}
* Mesajul contine fiecare numar natural din intervalul [1, m] cel putin o data.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. cifru2.in |_. cifru2.out |
| 6 3
2 1 3 3 2 1
1 3 1 3 2 2
| 2
3 1 2
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
