== 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, matricile interesante sunt acele matrici 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$ 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$.

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