Stars✨️

Ne aflăm pe Terra. Știm de la orele de geografie că planeta noastră este formată din zone cu apă și zone de uscat. Fiind programatori, vom reduce această lume la o matrice.

Fie matricea binară $A$ cu $N$ linii și $M$ coloane, unde:

• $0$ reprezintă o zonă cu apă,
• $1$ reprezintă o zonă de uscat.

O insulă este un grup de celule $1$ conectate prin oricare dintre cele $8$ direcții (Nord, Sud, Est, Vest, Nord-Vest, Nord-Est, Sud-Vest, Sud-Est). Cunoaștem numărul total de insule de pe Pământ, acestea fiind $K$ la număr.
Analog, un lac, un fluviu, o mare sau un ocean este un grup de celule $0$ conectate pe aceleași $8$ direcții. Pentru simplitate, aceste zone le vom numi lacuri.

Pe pământ trăiesc doi îndrăgostiți, Răzvan și Andreea. Aceștia se află pe insule diferite, astfel Răzvan pornește într-o expediție pentru a ajunge la jumătatea sa.
Traversarea apei este periculoasă, așa că Răzvan va înainta doar pe timpul zilei. Mai precis:

• Ziua poate traversa lacurile.
• Noaptea trebuie să se oprească pe o insulă.

Fiecare insulă are un număr cunoscut de stele vizibile pe cer noaptea. Andreea le adoră, așa că Răzvan îi va aduce cât mai multe.
De fiecare dată când ajunge pe o insulă, el va colecta toate stelele vizibile acolo, iar acea insulă nu va mai avea stele dacă Răzvan revine ulterior.
Odată ce ajunge la Andreea, călătoria sa se oprește și îi oferă toate stelele strânse până în acel moment.

Avem $Q$ întrebări de forma: $R_x, R_y, A_x, A_y$.

Pentru fiecare întrebare, trebuie să determinăm:
Care este numărul maxim de stele pe care Răzvan le poate colecta pornind de pe insula pe care acesta se află, care cuprinde coordonatele $(R_x, R_y)$ până la insula Andreei, insula care cuprinde coordonatele $(A_x, A_y)$?

Date de intrare

Pe prima linie din fișierul de intrare stars.in se află patru numere întregi, $N, M, Q$ și $K$, având semnificația descrisă în enunț.
Următoarele $N$ linii conțin câte $M$ cifre, reprezentând valorile matricei binare $A$.
Pe linia $N+2$ se află $K$ numere întregi, fiecare indicând numărul de stele de pe câte o insulă de pe Terra.
Începând cu linia $N+3$, urmează $Q$ linii, fiecare conținând patru numere întregi: $R_x, R_y, A_x$ și $A_y$, reprezentând coordonatele îndrăgostiților.

Date de ieșire

Pentru fiecare întrebare, se va afișa pe câte o linie în fișierul stars.out numărul maxim de stele pe care Răzvan le poate colecta pentru Andreea.

Restricții și precizări

• $3 \leq N \cdot M \leq 1 \ 000 \ 000$
• $1 \leq Q \leq 200 \ 000$
• $2 \leq K \leq 50 \ 000$. Se garantează că există $K$ insule pe Terra.
• $3 \leq$ numărul de insule și lacuri $\leq 100 \ 001$
• $1 \leq$ numărul de stele de pe o insulă $\leq 1 \ 000$
• Dacă am ajuns pe insula Andreei, vom colecta toate stelele de pe insula ei, apoi îi vom dărui toate stelele colectate până în acel moment.
• Pentru a identifica insulele și a determina numărul de stele de pe fiecare dintre ele, vom atribui fiecărei insule coordonata sa minimă în ordine lexicografică. Astfel, prima insulă va fi cea care are cea mai mică coordonată în ordine lexicografică, a doua insulă va fi cea cu a doua cea mai mică coordonată în ordine lexicografică și așa mai departe.

Exemplul 1

stars.in

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

stars.out

16
16
16

Explicație

În figura alăturată au fost evidențiate insulele, respectiv lacurile.
Există $4$ insule, respectiv $3$ lacuri.
Dacă vrem să rezolvăm ultima întrebare, un răspuns corect ar fi să pornim de pe insula maro, fiind și insula lui Răzvan, apoi să intrăm pe insula de culoare roșie, apoi să intrăm pe insula de culoare portocalie, iar ultima insulă în care o să intrăm va fi cea de culoare gri, insula Andreei.

Exemplul 2

stars.in

9 9 3 3
1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 0 1 1 1 1 1 0 1 
1 0 1 0 0 0 1 0 1
1 0 1 0 1 0 1 0 1
1 0 1 0 0 0 1 0 1
1 0 1 1 1 1 1 0 1
1 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1
1 2 3
1 1 3 3
5 5 5 3
1 1 5 5

stars.out

3
5
6