Divinitate

Pe îndepărtatul tărâm Algorithmicus, pacea este pe cale să se încheie...

Tărâmul este format din uscat și apă. Uscatul este controlat în integralitate de $K$ regate (numerotate de la $1$ la $K$) în timp ce apa nu este controlată de niciun regat.

Tărâmul este reprezentat printr-o matrice $D$ cu $N$ linii și $M$ coloane. Fiecare celulă a sa conține:

• fie un număr natural pozitiv reprezentând indicele regatului căruia îi aparține, dacă celula corespunde unei zone de uscat a tărâmului;
• fie valoarea $0$, dacă celula corespunde unei zone de apă a tărâmului.

Spunem că două celule se învecinează dacă au o latură comună.

Un lanț de celule este o listă de celule cu proprietatea că oricare două celule consecutive din listă se învecinează.

Două regate $A$ și $B$ se învecinează dacă se îndeplinește cel puțin una dintre condițiile:

• există o celulă a regatului $A$ și o celulă a regatului $B$ care se învecinează;
• există o celulă a regatului $A$ și o celulă a regatului $B$ care sunt capetele unui lanț de celule format numai din celule de apă, cu excepția capetelor.

Fiecare regat $i$ are o putere de luptă proprie, descrisă printr-un întreg pozitiv, notat cu $V_i$.

Un regat $A$ poate ataca un alt regat vecin $B$ doar dacă puterea sa actuală este mai mare sau egală ca puterea regatului vecin ($V_A \geq V_B$). După cucerirea regatului $B$, întregul său teritoriu devine parte din teritoriul regatului $A$, iar întreaga sa putere de luptă se adaugă la puterea totală a regatului $A$ (adică $V_A \gets V_A + V_B$).

Un regat $A$ poate cuceri regate succesiv, extinzându-și teritoriul și mărindu-și puterea până când condiția mai sus menționată nu se mai îndeplinește în raport cu niciun alt regat. În această situație, dacă regatul $A$ nu ocupă deja întregul uscat, regele său (și liderul bisericesc) poate invoca benevolența divinității, cerându-i să-i crească puterea regatului ($V_A$) cu minimul necesar care să-i permită reluarea campaniei de cuceriri.

Cerință

Se dă un întreg $C$, numărul cerinței de rezolvat, după cum urmează:

• Dacă $C = 1$ atunci se dau $Q$ interogări de forma $S_i$. Pentru fiecare dintre aceste interogări calculați, pornind de la starea inițială, care este puterea maximă pe care regatul $S_i$ o poate atinge fără invocarea divinității. Ca excepție, dacă regatul $S_i$ poate ocupa întregul uscat fără invocarea divinității, atunci răspunsul va fi $0$.
• Dacă $C = 2$ atunci se dau $Q$ interogări de forma $(S_i, F_i)$. Pentru fiecare dintre aceste interogări calculați, pornind de la starea inițială, cantitatea minimă de putere pe care regatul $S_i$ trebuie să o primească din partea divinității pentru a reuși să cucerească regatul $F_i$.
• Dacă $C = 3$ atunci se dau $Q$ interogări de forma $(S_i, F_i)$. Pentru fiecare dintre aceste interogări calculați, pornind de la starea inițială, numărul minim de situații în care divinitatea trebuie să-și manifeste benevolența față de regatul $S_i$ pentru a reuși să cucerească regatul $F_i$.

Date de intrare

Fișierul de intrare divinitate.in conține pe prima linie întregii $C$, $N$, $M$ și $K$. Pe fiecare dintre următoarele $N$ linii se află câte $M$ întregi separați prin câte un spațiu, reprezentând matricea $D$. Pe următoarea linie se află puterile inițiale ale regatelor: $V_1, V_2, \ldots, V_K$, separați prin câte un spațiu. Pe următoarea linie se află se află întregul $Q$. Fiecare dintre următoarele $Q$ linii conțin unul sau doi întregi: $S_i$ sau $S_i$ și $F_i$, în funcție de $C$).

Date de ieșire

Fișierul de ieșire divinitate.out va conține $Q$ linii, linia $i$ conținând câte un număr întreg, răspunsul pentru interogarea $i$.

Restricții și precizări

• $1 \leq C \leq 3$
• $1 \leq N, M \leq 1 \ 000$
• $1 \leq K \leq N \cdot M$
• $0 \leq D_{i,j} \leq K$, pentru $1 \leq i \leq N$ și $1 \leq j \leq M$
• $1 \leq Q \leq 300 \ 000$
• $1 \leq V_i \leq 10^{18}$, pentru $1 \leq i \leq K$
• $1 \leq S_i, F_i \leq K$ și $S_i \neq F_i$, pentru $1 \leq i \leq Q$
• Un regat poate fi format din mai multe zone izolate pe hartă (exclave). Cucerirea unei exclave implică cucerirea întregului regat.
• Se garantează că inițial fiecare dintre cele $K$ regate controlează cel puțin o celulă.
• Apa nu aparține niciunui regat, nu poate fi cucerită de vreun regat și poate fi privită strict ca pe o cale de deplasare.

Tabelul de mai jos reprezintă distribuția de punctaj în funcție de restricții și cerință:

Exemplul 1

divinitate.in

1 5 5 6
6 1 1 0 2
1 1 0 0 2
1 0 0 2 2
0 0 3 4 4
5 5 4 4 6
100 2 3 3 1 7
6
1
2
3
4
5
6

divinitate.out

0
16
16
16
1
16

Exemplul 2

divinitate.in

2 5 5 6
6 1 1 0 2
1 1 0 0 2
1 0 0 2 2
0 0 3 4 4
5 5 4 4 6
100 2 3 3 1 7
6
1 4
2 1
3 1
4 3
5 1
6 2

divinitate.out

0
84
84
0
84
0

Exemplul 3

divinitate.in

3 5 5 6
6 1 1 0 2
1 1 0 0 2
1 0 0 2 2
0 0 3 4 4
5 5 4 4 6
100 2 3 3 1 7
6
1 4
2 1
3 1
4 3
5 1
6 2

divinitate.out

0
1
1
0
2
0

Explicație

Regatul $6$ este format din două exclave. Cucerirea uneia conduce la cucerirea imediată a celeilalte.

Primul regat poate cuceri toate celelalte regate fără invocarea divinității și va avea o putere finală de $116$. Ca excepție, răspunsul afișat pentru prima cerință va fi $0$.

Regatele $2$, $3$, $4$ și $6$ pot cuceri toate celelalte regate cu excepția primului regat fără invocarea divinității. La acel moment ele ar avea puterea $16$.

Al cincilea regat nu poate cuceri niciun alt regat fără invocarea divinității. Pentru a putea cuceri primul regat sunt necesare două invocații ale divinității. După prima invocare, regatului îi crește puterea cu $1$. După a doua invocare, regatului îi crește puterea cu încă $83$.