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.
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.
Cerinţă
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.
Date de intrare
Fişierul de intrare xor2.in conţine pe prima linie T şi P, cu semnificaţia de mai sus. Fiecare din următoarele T linii conţine câte 4 numere naturale L1 C1 L2 C2, despărţite printr-un spaţiu, reprezentând coordonatele unei submatrice.
Date de ieşire
Fişierul de ieşire xor2.out conţine exact T linii. Linia cu numărul i conţine suma modulo P a elementelor celei de a i-a submatrice din fişierul de intrare.
Restricţii
• 1 ≤ T ≤ 20 000
• Pentru fiecare submatrice din cele T, 1 ≤ L1 ≤ L2 ≤ 108 şi 1 ≤ C1 ≤ C2 ≤ 108
• P este număr prim mai mic sau egal decât 30 000.
• Liniile şi coloanele matricei sunt numerotate începând cu 1.
