== include(page="template/taskheader" task_id="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~} ≥ 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~} ← 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.
h2. Cerinţe
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~}$.
Poveste şi cerinţă...
h2. 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~}, ..., 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$).
Fişierul de intrare $divinitate.in$ ...
h2. 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$.
În fişierul de ieşire $divinitate.out$ ...
h2. Restricţii
* $1 ≤ C ≤ 3$
* $1 ≤ N, M ≤ 1 000$
* $1 ≤ K ≤ N * M$
* $0 ≤ D{~i,j~} ≤ K$, pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$
* $1 ≤ Q ≤ 300 000$
* $1 ≤ V{~i~} ≤ 10^18^$, pentru $1 ≤ i ≤ K$
* $1 ≤ S{~i~}, F{~i~} ≤ K$ şi $S{~i~} ≠ F{~i~}$, pentru $1 ≤ i ≤ 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.
table(example). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $1$ | $C = 1$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $2$ | $2$ | $C = 2$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $3$ | $3$ | $C = 3$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $4$ | $2$ | $C = 1$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $5$ | $3$ | $C = 2$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $6$ | $4$ | $C = 3$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$, $D{~i,j~} ≠ 0$ pentru $1 ≤ i ≤ N$ şi $1 ≤ j ≤ M$|
| $7$ | $2$ | $C = 1$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$|
| $8$ | $3$ | $C = 2$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$|
| $9$ | $4$ | $C = 3$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 100$|
| $10$ | $2$ | $C = 1$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$|
| $11$ | $3$ | $C = 2$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$|
| $12$ | $4$ | $C = 3$, $N ≤ 100$, $M ≤ 100$, $Q ≤ 30 000$|
| $13$ | $5$ | $C = 1$, oricare două regate se învecinează|
| $14$ | $9$ | $C = 2$, oricare două regate se învecinează|
| $15$ | $13$ | $C = 3$, oricare două regate se învecinează|
| $16$ | $4$ | $C = 1$, $Q ≤ 30 000$|
| $17$ | $6$ | $C = 2$, $Q ≤ 30 000$|
| $18$ | $9$ | $C = 3$, $Q ≤ 30 000$|
| $19$ | $4$ | $C = 1$|
| $20$ | $7$ | $C = 2$|
| $21$ | $10$ | $C = 3$|
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. divinitate.in |_. divinitate.out |
| 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
| 0
16
16
16
1
16
|
| 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
| 0
84
84
0
84
0
|
| 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
| 0
1
1
0
2
0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţii
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$.
h3. Explicaţie
!problema/divinitate?divinitate_exemplu.png!
...
== include(page="template/taskfooter" task_id="divinitate") ==
