Matricen

matricen

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

Anul acesta Mos Craciun v-a facut un cadou mai ciudat, anume o matrice binara $A$ cu $N$ linii si $N$ coloane. Totusi, matricele interesante sunt acele matrice care pe fiecare linie au numai elemente egale. Dan Craciun, fratele lui Mos Craciun va roaga sa il ajutati cu o problema pentru a va pune o vorba buna la mos. Dan va pune la dispozitie $Q$ submatrice ale matricei initiale si va roaga sa aflati pentru fiecare submatrice numarul minim de operatii care trebuie efectuate astfel incat submatricea rezultata in urma efectuarii operatiilor sa fie interesanta. In cadrul unei operatii puteti interschimba oricare doua elemente din submatrice. Dan va furnizeaza coltul stanga-sus al submatricei precum si coltul dreapta-jos al ei. Daca $(L1, C1)$ este coltul stanga-sus si $(L2, C2)$ este coltul dreapta jos, atunci submatricea este formata din elemetele $A{~i,j~}$, unde $L1 ≤ i ≤ L2$ si $C1 ≤ j ≤ C2$.

Anul acesta Mos Craciun v-a facut un cadou mai ciudat, anume o matrice binara $A$ cu $N$ linii si $N$ coloane. Totusi, matricile interesante sunt acele matrici care pe fiecare linie au numai elemente egale. Dan Craciuc, fratele lui Mos Craciun va roaga sa il ajutati cu o problema pentru a va pune o vorba buna la mos. Dan va pune la dispozitie $Q$ submatrici ale matricei initiale si va roaga sa aflati pentru fiecare submatrice numarul minim de operatii care trebuie efectuate astfel incat submatricea rezultata in urma efectuarii operatiilor sa fie interesanta. In cadrul unei operatii puteti interschimba oricare doua elemente din submatrice. Dan va furnizeaza coltul stanga-sus al submatricei precum si coltul dreapta-jos al ei. Daca $(L1, C1)$ este coltul stanga-sus si $(L2, C2)$ este coltul dreapta jos, atunci submatricea este formata din elemetele $A{~i,j~}$, unde $L1 ≤ i ≤ L2$ si $C1 ≤ j ≤ C2$.

h2. Date de intrare

* $1 ≤ N ≤ 300$
* $1 ≤ Q ≤ 50 000$

* Pentru $50%$ din teste $Q ≤ 1000$

h2. Exemplu
table(example). |_. matricen.in |_. matricen.out |

| 3 3
  0 0 0
  0 1 0
  1 1 0
  2 1 3 3
  1 2 2 3
  1 1 1 3
| 1
  -1
  0

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Pentru prima submatrice se poate interschimba elementul de pe pozitia $(2, 2)$ cu cel de pe pozitia $(3, 3)$. Pentru a doua submatrice nu avem solutie de aceea afisam $-1$. A treia submatrice contine deja o linie in care toate elementele sunt egale, deci nu mai trebuie sa efectuam nicio operatie.

...

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

4845