Serpuit

Gușterul, Girafa și Țestoasa vor să se plimbe cu mașina prin cartierul lor! Cartierul poate fi privit ca o matrice pătratică de latură $N$. Pentru ca fiecare drum să fie o aventură memorabilă, drumurile vor urma o parcurgere șerpuită.

O parcurgere șerpuită vizitează elementele matricei pe diagonale paralele cu diagonala secundară. Începând dintr-o celulă de start, se parcurg toate elementele de pe diagonala curentă, apoi se trece la diagonala următoare. Pentru a menține continuitatea, direcția se inversează la fiecare pas: o diagonală este parcursă în sensul spre $(N, 1)$, iar următoarea în sens opus, procesul repetându-se până la final.

Pentru claritate, ilustrăm mai jos două parcurgeri șerpuite într-o matrice pătratică de latură $4$, prima, care reprezintă parcurgerea șerpuită începând cu celula $(1, 1)$, iar, a doua, care reprezintă parcurgerea șerpuită începând cu celula $(2, 3)$:

Cerință

Gușterul, Girafa și Țestoasa vor efectua $T$ drumuri, despre care se știu:

• $x \ y \ k \ \text{val}$ - se va efectua o parcurgere șerpuita, începând cu celula $(x, y)$, care cuprinde primele $k$ celule parcurse din parcurgerea curentă, cu o mașina căreia îi ia $\text{val}$ secunde să se deplaseze dintr-o celulă în alta.

Dupa efectuarea tuturor parcurgerilor, cei 3 prieteni vin cu $Q$ întrebări de forma: câte secunde am stat in celula $(a, b)$?

Date de intrare

Pe prima linie se vor afla $N$ (dimensiunea matricei), $T$ (numărul de drumuri efectuate) și $Q$ (numărul de intrebari).

Pe următoarele $T$ linii se vor afla câte $4$ numere $x, y, k$ și $\text{val}$, care descriu un drum.

Pe următoarele $Q$ linii se vor afla câte două numere $a$ și $b$, care reprezintă o celulă despre care cei trei prieteni vor să afle cât timp au petrecut în zona respectivă.

Date de ieșire

Se vor afișa $Q$ linii, unde pe linia $i \ (1 \leq i \leq Q)$ se va afla răspunsul la a $i$-a întrebare.

Restricții și precizări

• $1 \leq N \leq 1 \ 000 \ 000$
• $1 \leq T, Q \leq 200 \ 000$
• Pentru toate drumurile, $1 \leq x, y \leq N$ si $1 \leq \text{val} \leq 10^9$;
• Pentru toate drumurile, $1 \leq k \leq$ numărul maxim de celule care pot fi parcurse începând cu celula $(x, y)$;
• Pentru toate întrebările, $1 \leq a, b \leq N$.

Exemplu

stdin

4 2 3
1 1 12 10
2 3 7 8
2 1
4 4
3 3

stdout

10
0
18

Explicație

După toate operațiile, matricea va arăta astfel:

10 10 10 10
10 10 18 18
10 18 18 8
18 8 0 0