permutare2

Permutare2

== include(page="template/taskheader" task_id="permutare2") ==

Se dă o matrice cu m linii şi n coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la 2 la m sunt permutări circulare ale primei linii. Unei linii x (1 ≤ x ≤ m) i se pot aplica următoarele operaţii:
- o permutare circulară la stânga: elementul de pe poziţia i (1 < i ≤ n) se mută pe poziţia i-1, mai puţin primul primul element, care devine ultimul;
- o permutare circulară la dreapta: elementul de pe pozitia i (1 ≤ i < n) se mută pe poziţia i+1, mai puţin ultimul element care devine primul.
 

Se dă o matrice cu $m$ linii şi $n$ coloane, fiecare linie reprezentând o permutare. Se ştie că liniile de la $2$ la $m$ sunt permutări circulare ale primei linii. Unei linii $x (1 ≤ x ≤ m)$ i se pot aplica următoarele operaţii:
 
* o permutare circulară la stânga: elementul de pe poziţia $i (1 < i ≤ n)$ se mută pe poziţia $i-1$, mai puţin primul primul element, care devine ultimul;
* o permutare circulară la dreapta: elementul de pe pozitia $i (1 ≤ i < n)$ se mută pe poziţia $i+1$, mai puţin ultimul element care devine primul.
 

Scopul este să permutăm circular liniile, la stânga sau la dreapta, astfel încât în final toate liniile să fie egale, folosind un număr minim de operaţii.

h2. Date de intrare

 
h2. Cerinţa

Dându-se o matrice cu proprietatea din enunţ se cere să se determine numărul minim de operaţii necesare pentru a ajunge la o matrice în care toate liniile sunt egale.

h2. Date de intrare
 
Fişierului de intrare $permutare2.in$ conţine pe prima linie două numere naturale $n$ şi $m$, reprezentând numărul de coloane şi numărul de linii ale matricei. Pe a doua linie a fişierului de intrare se află n numere naturale, reprezentând permutarea de pe prima linie a matricei. Pe următoarele m-1 linii, se află câte un număr natural cuprins între $0$ şi $n-1$. Al $i$-lea $(0 < i < m)$ dintre aceste numere reprezintă numărul de poziţii cu care este permutată circular la dreapta a $(i+1)$-a linie faţă de linia 1.
 

h2. Date de ieşire

Pe prima linie a fişierului de ieşire permutare.out se va scrie un singur număr natural reprezentând numărul minim de operaţii necesare.

Pe prima linie a fişierului de ieşire $permutare2.out$ se va scrie un singur număr natural reprezentând numărul minim de operaţii necesare.

h2. Restricţii

* 1 ≤ n, m ≤ 100 000

* $1 ≤ n, m ≤ 100.000$

* Două linii dintr-un tablou sunt egale dacă elementele aflate pe aceeaşi coloană sunt egale.
h2. Exemplu

Matricea va fi:

3 1 4 2 6 5
5 3 1 4 2 6
5 3 1 4 2 6
2 6 5 3 1 4
2 6 5 3 1 4

$3 1 4 2 6 5$
$5 3 1 4 2 6$
$5 3 1 4 2 6$
$2 6 5 3 1 4$
$2 6 5 3 1 4$

Dacă permutăm circular la dreapta prima linie cu o poziţie, iar liniile 4 şi 5 le permutăm la stânga cu două poziţii, vom obţine din 5 operaţii o matrice cu toate liniile egale între ele. Liniile vor fi determinate de permutarea: 5 3 1 4 2 6

Dacă permutăm circular la dreapta prima linie cu o poziţie, iar liniile $4$ şi $5$ le permutăm la stânga cu două poziţii, vom obţine din $5$ operaţii o matrice cu toate liniile egale între ele. Liniile vor fi determinate de permutarea: $5 3 1 4 2 6$

== include(page="template/taskfooter" task_id="permutare2") ==

9939