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 iesire

Î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 și precizări

• 1 ≤ N, M ≤ 2 000
• 1 ≤ Q ≤ 5 000
• 1 ≤ x1 ≤ x2 ≤ N
• 1 ≤ y1 ≤ y2 ≤ M
• Pentru 52 de puncte din cele 100 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

camere.in

5 6
aabbcc
abbbcc
cbeaed
adeeed
affttz
3
1 1 5 6
2 1 4 5
3 3 5 6

camere.out

12
8
6

Explicații

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ă.