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, c1 c2 … cn, codificarea mesajului se realizează astfel: se înlocuieşte fiecare literă ci cu p( ci ), apoi şirul obţinut p( c1 ) p( c2 ) … p( cn ) se roteşte spre dreapta, făcând o permutare circulară cu d poziţii rezultând şirul p( cn-d+1 ) … p( cn-1 ) p( cn ) p( c1 ) p( c2 )… p( cn-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 cifru1.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 cifru1.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), …, p(m) separate prin câte un spaţiu.
Restricţii
n ≤ 100 000
m ≤ 9999
Mesajul conţine fiecare număr natural din intervalul [1, m] cel puţin o dată.
Pentru teste cu m ≤ 5 se acordă 40 de puncte din care 20 pentru teste şi cu n ≤ 2000.