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

Lui Hadrianus îi plac matricele infinite care sunt generate după o anumită regulă. Înainte de primul baraj, el se gândeşte la o astfel de matrice, în care elementul de pe linia $i$ şi coloana $j$ este egal cu $i xor j$. Hadrianus doreşte să determine suma elementelor pentru unele submatrici ale matricii formate după regula de mai sus.
Se numeşte submatrice de coordonate $(L1, C1, L2, C2)$, cu $1 ≤ L1 ≤ L2$ şi $1 ≤ C1 ≤ C2$, o zonă dreptunghiulară din matrice care are colţul stânga-sus pe linia $L1$ şi coloana $C1$ şi colţul dreapta-jos pe linia $L2$ şi coloana $C2$.

Lui Hadrianus îi plac matricele infinite care sunt generate după o anumită regulă. Înainte de primul baraj, el se gândeşte la o astfel de matrice, în care elementul de pe linia $i$ şi coloana $j$ este egal cu $i xor j$. Hadrianus doreşte să determine suma elementelor pentru unele submatrici ale matricii formate după regula de mai sus. Se numeşte submatrice de coordonate $(L1, C1, L2, C2)$, cu $1 ≤ L1 ≤ L2$ şi $1 ≤ C1 ≤ C2$, o zonă dreptunghiulară din matrice care are colţul stânga-sus pe linia $L1$ şi coloana $C1$ şi colţul dreapta-jos pe linia $L2$ şi coloana $C2$.
 

!> problema/xor?xor.png 70%!

Operaţia $xor$ reprezintă operaţia de disjuncţie exclusivă realizată pe biţii operanzilor. În Pascal, operatorul corespunzător este $xor$, iar în C/C++ acest operator este $^$. De exemplu, $20 xor 14 = 26$. Matricea formată are primele elemente conform figurii alăturate.
Scrieţi un program care citeşte coordonatele a $T$ submatrice şi afişează pentru fiecare dintre aceste submatrice suma elementelor sale modulo $P$ (restul împărţirii sumei la $P$), unde $P$ este un număr prim.

* $P$ este număr prim mai mic sau egal decât $30 000$
* Liniile şi coloanele matricei sunt numerotate începând cu $1$
* La evaluare se vor folosi $10$ teste. Ele vor avea următoarea structură:

** Pentru primele $2$ teste, $T ≤ 100$ şi $L2,C2 ≤ 100$
** Pentru testele $3$ şi $4$, $L2,C2 ≤ 1000$

** Pentru primele $2$ teste, $T ≤ 100$ şi $L2, C2 ≤ 100$
** Pentru testele $3$ şi $4$, $L2, C2 ≤ 1000$

** Pentru testele $5$ şi $6$, $L1 = L2$
** Pentru testele $7$ şi $8$, $P = 2$
** Celelalte două teste respectă limitele de mai sus şi nu au nicio particularitate specială

h3. Explicaţie

Prima submatrice este formată din elementele $2$, $5$, $1$ şi $6$. Suma modulo $29473$ a acestor elemente este:
$(2 + 5 + 1 + 6) % 29473 = 14$.

Prima submatrice este formată din elementele $2$, $5$, $1$ şi $6$. Suma modulo $29473$ a acestor elemente este: $(2 + 5 + 1 + 6) % 29473 = 14$.

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

4794