Prošlo je vreme igre, uživanja i razonode. Prošlo je vreme malih matrica. Danas su računari neverovatno brzi i mogu izvršiti i do $10^{100}$ komandi u sekundi. Iz tog razloga komisija vam je spremila jednostavan zadatak sa jednom matricom i mnogo interesantnih upita.

U ovom zadatku vam je data matrica $A$ dimenzije $n \times m$ - matrica ima tačno $n$ vrsta i tačno $m$ kolona. Vrste su numerisane brojevima od $1$ do $n$ odozgo nadole a kolone su numerisane brojevima od $1$ do $m$ sleva udesno. Za svako $i$ ($1 \leq i \leq n$) i $j$ ($1 \leq j \leq m$) vrednost na poziciji ($i,j$) u matrici $A$ (tj. na polju u preseku $i$-te vrste $j$-te kolone) je definisana na sledeći način :

$A_{i,j} = i \ \text{xor} \ j$

gde operacija $X \ \text{xor} \ Y$ predstavlja ekskluzivnu disjunkciju brojeva $X$ i $Y$.

Potrebno je odgovoriti na $q$ upita oblika: Naći vrednost $\text{xor}$-a svih brojeva u podmatrici matrice $A$ sa gornjim levim temenom $(x_l,y_l)$ i donjim desnim temenom $(x_r,y_r)$. Podmatrica matrice $A$ sa navedenim ograničenjima obuhvata sve elemente $A_{i,j}$ takve da važi $x_l \leq i \leq x_r$ , $y_l \leq j \leq y_r$.

Opis ulaza

U prvoj liniji standardnog ulaza nalaze se brojevi $n, m, q$, broj vrsta matrice $A$, broj kolona matrice $A$ i broj upita na koje je potrebno odgovoriti. Narednih $q$ linija sadrže po četiri broja, koji predstaljaju redom vrstu gornjeg levog temena podmatrice, kolonu gornjeg levog temena podmatrice, vrstu donjeg desnog temena podmatrice i kolonu donjeg desnog temena podmatrice.

Opis izlaza

Na standardnom izlazu u $q$ redova odgovoriti na upite opisane u tekstu zadatka, tačnije u $i$-a liniji standardnog izlaza ispisati rešenje $i$-tog upita.

Primer

Ulaz

4 5 3
1 1 3 3
2 3 4 5
2 3 2 4

Izlaz

0
7
7

Objašnjenje primera

Matrica A je dimenzije $4 \cdot 5$ i ima oblik:

                  0 3 2 5 4
                  3 0 1 6 7
                  2 1 0 7 6
                  5 6 7 0 1

Prvi upit zadrži podmatricu sa gornjim levim temenom ($1,1$) i donjim desnim ($3,3$). Rešenje ovog upita je $\text{ xor }$ svih brojeva u podmatrici, odnosno : $0 \text{ xor } 3 \text{ xor } 2 \text{ xor } 3 \text{ xor } 0 \text{ xor } 1 \text{ xor } 2 \text{ xor } 1 \text{ xor } 0 = 0$

Treći upit sadrži samo dva broja $1$ i $6$, tako da je rešenja za ovaj primer $1 \text{ xor } 6 =7$

Ograničenja

$1 \leq n,m \leq 10^9$

$1 \leq q \leq 10^5$

Podzadaci

Test primeri su podeljeni u četiri disjunktne grupe.

U primerima vrednim 20 poena važiće ograničenje $1\leq n,m,q \leq 100$.

U primerima vrednim 20 poena važiće ograničenje $1\leq n,m \leq 1000$.

U primerima vrednim 30 poena važiće ograničenje $1\leq n,m \leq 10^6$.

U primerima vrednim 30 poena nema dodatnih ograničenja.

Napomena

Operator ekskluzivne disjunkcije u Pascal-u je označen sa xor, dok u C++ ga zapisujemo pomoću simbola ^. Ova operacija $x \ \text{xor} \ y$ se za nenegativne cele brojeve $x,y$ definiše na sledeći način: prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa $a_1, \ldots, a_k$ i $b_1, \ldots b_k$. Zatim se za svaku poziciju $i \in \{1, \ldots, k \}$ računa $c_i$ pomoću sledećih pravila:

• Za $a_i = 0, b_i = 0$ važi $c_i = 0$
• Za $a_i = 0, b_i = 1$ važi $c_i = 1$
• Za $a_i = 1, b_i = 0$ važi $c_i = 1$
• Za $a_i = 1, b_i = 1$ važi $c_i = 0$

Niz binarnih cifara $c_1, \ldots, c_k$ (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja $x \ \text{xor} \ y$.