Áles se află într-un castel, reprezentat printr-o matrice A cu N linii și N coloane, fiecare element corespunzând unei camere. Fiecare cameră are asociat câte un număr natural de la 1 la N, care este memorat în elementul corespunzător din matrice. Oricare două camere cu același număr asociat sunt conectate printr-un tunel. De asemenea, fiecare cameră este conectată printr-o ușă cu o cameră vecină, elementele corespunzătoare acestora fiind în matrice pe acceași linie și pe coloane alăturate sau pe aceeași coloană și pe linii alăturate. Scopul lui Áles este să viziteze toate camerele, fiecare cel puțin o dată, astfel încât numerele asociate lor, în ordinea vizitării acestora, să formeze un şir crescător, începând de la 1.

Áles alege la început o cameră care are asociat numărul 1. Din fiecare cameră ce corespunde unui element \(A_{i,j}\) el poate vizita:

• folosind un tunel, orice cameră ce corespunde unui element \(i’,j’\) astfel încât \(A_{i’,j’} = A_{i,j}\).
• folosind o uşă, orice camera vecină cu un număr asociat consecutiv, deci care corespunde unui element \(i’,j’\) astfel încât \( |i’-i|+|j’-j|=1 \) și \(A_{i’,j’}=A_{i,j}+1\).
• folosind un teleportor, în orice cameră cu numărul asociat \(A_{i,j}+1\), la această metodă de deplasare putând să recurgă numai dacă nu poate ajunge la o astfel de cameră utilizând un tunel sau o uşă.

Ați înțeles, Áles doreşte să folosească teleportorul de cât mai puţine ori! El calculează mai întâi numărul minim necesar de teleportări pentru configurația inițială a camerelor, apoi face, pe rând, Q transformări succesive ale configurației, prin schimbarea numărului asociat pentru câte o cameră; după fiecare astfel de transformare, calculează din nou numărul minim necesar de teleportări pentru configurația respectivă.

Cerința

Pentru configurația inițială, precum și după fiecare dintre cele Q transformări ale acesteia, în ordinea în care sunt realizate, determinați numărul minim de teleportări necesare pentru ca Áles să își îndeplinească scopul.

Date de intrare

Fișierul de intrare teleportor.in conține:

• pe prima linie numerele naturale N și K, cu semnificația din enunț.
• pe următoarele N linii câte N numere naturale, reprezentând numerele asociate inițial camerelor, în ordinea corespunzătoare elementelor din matrice, linie cu linie, de sus în jos, și de la stânga la dreapta pe fiecare linie.
• pe următoarea linie numărul Q, cu semnificația din enunț.
• pe următoarele Q linii câte trei numere naturale i j c, cu semnificația că \(A_{i,j}\) este schimbat cu c.

Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire teleportor.out va conţine pe Q+1 linii, numerele minime de teleportări determinate conform cerinței, câte un singur număr pe linie, în ordinea indicată.

Restricții și precizări

• 1 ≤ N ≤ 1.000
• 1 ≤ K ≤ N2
• 1 ≤ Q ≤ 250.000
• 1 ≤ i,j ≤ N
• În configuraţia iniţială şi după fiecare transformare a acesteia se garantează că fiecare număr de la 1 la K este asociat cel puţin unei camere.
• Pentru 29 puncte, N, K, Q ≤ 50
• Pentru 23 puncte, N, Q ≤ 100
• Pentru 20 puncte, K = N2-1
• Pentru 28 puncte, fără restricții suplimentare.
• Datorită dimensiunilor mari ale fișierelor, nu au fost încărcate toate testele.

Exemplu

teleportor.in

3 3
2 1 1
1 2 1
3 1 3
2
3 2 3
2 1 2

teleportor.out

1
0
0

Explicație

Înainte de prima operație un posibil drum care obține o singură teleportare poate fi: (1, 2) → (1, 3) → (2, 3) → (3, 2) → (2, 1) → (1, 1) → (2, 2) → (3, 1) → (3, 3).

Teleportarea are loc la pasul (2, 2) → (3, 1).

După prima operație, camerele sunt numerotate conform:

2 1 1
1 2 1
3 3 3

Un posibil drum care nu necesită nicio teleportare poate fi: (1, 2) → (1, 3) → (2, 3) → (2, 1) → (1, 1) → (2, 2) → (3, 2) → (3, 1) → (3, 3).

După a doua operație, camerele sunt numerotate conform:

2 1 1
2 2 1
3 3 3

Un posibil drum care nu necesită nicio teleportare poate fi: (1, 2) → (1, 3) → (2, 3) → (2, 2) → (2, 1) → (1, 1) → (2, 1) → (3, 1) → (3, 2) → (3, 3).