== include(page="template/taskheader" task_id="petic") ==

Se da o matrice binara cu linii de la $0$ la $nrLin - 1$ si coloane de la $0$ la $nrCol - 1$, respectiv $Q$ intrebari independente, de forma $i j k$: "Sa presupunem ca schimbam in $0$ totii bitii de $1$ din subpatratul de latura de $k$ cu coltul stanga-sus pe linia $i$ si coloana $j$. Care e numarul total de linii si coloane ale noii matrice care mai au macar un bit $1$?"

Se da o matrice binara cu linii de la $0$ la $nrLin - 1$ si coloane de la $0$ la $nrCol - 1$, respectiv $Q$ intrebari independente, de forma $X{~1~} Y{~1~} X{~2~} Y{~2~}$: "Sa presupunem ca schimbam in $0$ totii bitii de $1$ din submatricea cu coltul stanga-sus pe linia $X{~1~}$ si coloana $Y{~1~}$ si coltul dreapta-jos pe linia $X{~2~}$ si coloana $Y{~2~}$. Care e numarul total de linii si coloane ale noii matrice care mai au macar un bit $1$?"

h2. Date de intrare

Fişierul de intrare $petic.in$ contine, pe prima linie, numarele $nrLin$, $nrCol$ si $Q$. Pe urmatoarele $nrLin$ linii se afla cate un sir de $nrCol$ biti. Pe urmatoarele $Q$ linii se afla cate trei numere $i j k$.

Fişierul de intrare $petic.in$ contine, pe prima linie, numarele $nrLin$, $nrCol$ si $Q$. Pe urmatoarele $nrLin$ linii se afla cate un sir de $nrCol$ biti. Pe urmatoarele $Q$ linii se afla cate patru numere $X{~1~} Y{~1~} X{~2~} Y{~2~}$.

h2. Date de ieşire

h2. Restricţii

* $0 ≤ i, j$
* $1 ≤ k, nrLin, nrCol$
* $i + k - 1 < nrLin$
* $j + k - 1 < nrCol$
 
table(example). |_. #test |_. max(nrLin, nrCol) |_. Q |
| 1* | 30 | 1.000 |
| 2 | 50 | 2.500 |
| 3 | 100 | 10.000 |
| 4 | 200 | 50.000 |
| 5* | 300 | 100.000 |
| 6 | 400 | 250.000 |
| 7 | 500 | 250.000 |
| 8 | 600 | 500.000 |
| 9 | 700 | 500.000 |
| 10* | 800 | 750.000 |
| 11 | 900 | 750.000 |
| 12 | 1.000 | 850.000 |
| 13 | 1.500 | 850.000 |
| 14* | 2.000 | 1.000.000 |
| 15 | 2.500 | 1.000.000 |
| 16 | 3.000 | 1.250.000 |
| 17 | 3.500 | 1.250.000 |
| 18* | 4.000 | 1.500.000 |
| 19 | 4.500 | 1.500.000 |
| 20 | 5.000 | 2.000.000 |

* *Se recomanda parsarea intrarii si iesirii!*
* $0 &le; X{~1~} &le; X{~2~} < nrLin$
* $0 &le; Y{~1~} &le; Y{~2~} < nrCol$
* *$nrLin &le; nrCol$*
* $1 &le; Q$
 
h2. Punctare
 
h3. Subtask de 3 puncte
 
* $nrCol &le; 100$
* $Q &le; 1.000$
 
h3. Subtask de 11 puncte
 
* $nrCol &le; 400$
* $Q &le; 100.000$
 
h3. Subtask de 23 de puncte
 
* Toate submatricele din intrebari sunt patratice $(X{~2~} - X{~1~} = Y{~2~} - Y{~1~})$
* $nrCol &le; 1.000$
* $Q &le; 1.000.000$
 
 
h3. Subtask de 24 de puncte
 
* Toate submatricele din intrebari sunt patratice $(X{~2~} - X{~1~} = Y{~2~} - Y{~1~})$
* $nrCol &le; 1.800$
* $Q &le; 1.500.000$
 
h3. Subtask de 26 de puncte
 
* $Q, nrLin * nrCol &le; 400.000$
 
h3. Subtask de 13 puncte
 
* $nrLin * nrCol &le; 3.240.000$
* $Q &le; 1.500.000$

h2. Exemplu

| 2 2 5
11
01

0 0 2
0 0 1
0 1 1
1 0 1
1 1 1

0 0 1 1
0 0 0 0
0 1 0 1
1 0 1 0
1 1 1 1

| 0
3
4
4
3
|

 
h3. Explicaţie
 
...

| 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
| 2
4
5
3
5
4
5
4
|
| 1 2 1
01
0 0 0 1
| 0
|

== include(page="template/taskfooter" task_id="petic") ==