Fişierul intrare/ieşire:	camere.in, camere.out	Sursă	Lot 2017 Baraj 1
Autor	Lucian Bicsi, Radu Muntean	Adăugată de	Eugenie Daniel Posdarascu •eudanip
Timp execuţie pe test	1.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Camere

Se dă o matrice de N linii şi M coloane care conţine numai litere mici ale alfabetului englez. Se defineşte o cameră ca o zonă maximală de celule din matrice ce conţin aceeaşi literă, conexă pe cele 4 direcţii: sus, jos, stânga, dreapta.

Ne interesează răspunsuri la întrebări de forma: “Câte camere sunt incluse complet sau parţial într-un dreptunghi dat, văzut ca o submatrice?”.

Date de intrare

Pe prima linie a fişierului de intrare camere.in se vor afla 2 numere N şi M separate prin câte un spaţiu, iar pe următoarele N linii câte M caractere din alfabetul englez (neseparate prin spaţii). Linia N+2 va conţine un număr Q, reprezentând numărul de întrebări, iar următoarele Q linii vor conţine câte 4 numere x1, y1, x2, y2 separate prin câte un spaţiu, reprezentând câte un dreptunghi definit prin punctele diagonal opuse de coordonate (x1,y1) şi (x2,y2).

Date de ieşire

În fişierul de ieşire camere.out se vor afla Q numere pe câte un rând, ce reprezintă răspunsurile la întrebări în ordinea în care au fost date în fişierul de intrare.

Restricţii

• 1 ≤ N,M ≤ 2000
• 1 ≤ Q ≤ 5000
• 1 ≤ x1 ≤ x2 ≤ N
• 1 ≤ y1 ≤ y2 ≤ M
• Pentru 70 de puncte din cele 130 de puncte se garantează că orice cameră poate fi inclusă complet în orice dreptunghi de query (adică orice cameră se poate translata astfel încât să fie în interiorul dreptunghiului respectiv).

Exemplu

Explicaţie

Avem 3 întrebări

Întrebarea 1 1 5 6 se referă la toată matricea, care are 12 camere.

Dreptunghiul 2 1 4 5 conţine 8 camere, dintre care 4 sunt complete şi alte 4 sunt incomplete.

Dreptunghiul 3 3 5 6 conţine 6 camere, dintre care 5 sunt complete şi o cameră este incompletă.

Cum se trimit solutii?