Petic

Se dă o matrice binară cu linii de la $0$ la $nrLin - 1$ și coloane de la $0$ la $nrCol - 1$, respectiv $Q$ întrebări independente, de forma $X_1, Y_1, X_2, Y_2$: "Să presupunem că schimbăm în $0$ toți biții de $1$ din submatricea cu colțul stânga-sus pe linia $X_1$ și coloana $Y_1$ și colțul dreapta-jos pe linia $X_2$ și coloana $Y_2$. Care e numărul total de linii și coloane ale noii matrice care mai au măcar un bit de $1$?"

Protocol de interacțiune

Concurentul va implementa funcția solve, cu următoarea semnătură:

std::vector<int> solve (int nrLin, int nrCol, int Q, 
						std::vector<std::string> matrix,
						std::vector<int> X1, std::vector<int> Y1, 
						std::vector<int> X2, std::vector<int> Y2);

Parametrii acestei funcții au următoarea semnificație:

• $nrLin$ numărul de linii ale matricei;
• $nrCol$ numărul de linii ale matricei; se garantează că $1 \le nrLin \le nrCol$
• $Q$ numărul de întrebări;
• $matrix$ matricea pe care se realizează interogările;
• vectorii $X1, Y1, X2, Y2$ conțin informațiile pentru întrebări; acești vectori au câte $Q$ elemente.

Funcția va întoarce un vector STL ce conține cele $Q$ numere cerute în rezultat, în ordine. Concurentul NU va implementa o funcție main.

Subtask 1 (3 puncte)

• $1 \le nrCol \le 100$
• $1 \le Q \le 1\ 000$

Subtask 2 (11 puncte)

• $1 \le nrCol \le 400$
• $1 \le Q \le 100\ 000$

Subtask 3 (23 puncte)

• Toate submatricele din intrebari sunt patratice $(X_2 - X_1 = Y_2 - Y_1)$
• $1 \le nrCol \le 1\ 000$
• $1 \le Q \le 1\ 000\ 000$

Subtask 4 (24 puncte)

• Toate submatricele din intrebari sunt patratice $(X_2 - X_1 = Y_2 - Y_1)$
• $1 \le nrCol \le 1\ 800$
• $1 \le Q \le 1\ 500\ 000$

Subtask 5 (26 puncte)

• $1 \le Q, nrLin \cdot nrCol \le 400\ 000$

Subtask 6 (13 puncte)

• $1 \le nrLin \cdot nrCol \le 3\ 240\ 000$
• $1 \le Q \le 1\ 500\ 000$

Exemple

Input

2 2 5
11
01
0 0 1 1
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1

Output

0
3
4
4
3

Input

2 3 8
100
111
0 0 1 1
0 0 0 0
1 0 1 0
0 1 1 2
0 1 0 1
1 1 1 1
0 2 0 2
1 2 1 2

Output

2
4
5
3
5
4
5
4

Input

1 2 1
01
0 0 0 1

Output

0