Soup has infiltrated Lakshy's top secret lab! Inside this lab are the secrets on how to survive the IB program. However, to get in Soup would need to bypass a sophisticated security lock. The security lock is an ~N~ by ~N~ matrix of cells. Soup has gained intel that the value of cell ~(i, j)~ (that is, the ~i^\text{th}~ row and ~j^\text{th}~ column) would be ~(i-1) \times N + j~ by default. To pass the lock, Soup will need to answer ~Q~ queries, the ~k^\text{th}~ asking for the value of a particular cell ~(y_k, x_k)~. Unfortunately, Soup was also informed that the numbers on the grid have been scrambled in ~K~ successive rotation operations! In the ~k^\text{th}~ operation, Lakshy rotates the square with top left corner ~(t_k, l_k)~ and bottom right corner ~(b_k, r_k)~ by 90 degrees clockwise. Overwhelmed by the difficulty, Soup cannot unlock the security lock, so he has come to you, his trusty accomplice, to help him!

Constraints

For all subtasks:

~1 \le N \le 10^9~

~1 \le K, Q \le 5 \times 10^3~

~1 \le t_k \le b_k \le N~

~1 \le l_k \le r_k \le N~

~b_k - t_k = r_k - l_k~

~1 \le y_k, x_k \le N~

Subtask 1 [20%]

~1 \le N \le 500~

~1 \le K \le 100~

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains three integers, ~N, K, Q~.

The next ~K~ lines each contain four integers, ~t_k, l_k, b_k, r_k~.

The next ~Q~ lines each contain two integers, ~y_k, x_k~.

Output Specification

For each of the ~Q~ queries, output on a separate line the value of cell ~(y_k, x_k)~.

Sample Input

3 2 2
1 1 3 3
2 2 3 3
3 2
1 2

Sample Output

3
4

Explanation

Before any rotations, the matrix looks like this:

1 2 3
4 5 6
7 8 9

After the first rotation, the matrix looks like this:

7 4 1
8 5 2
9 6 3

After the second rotation, the matrix looks like this:

7 4 1
8 6 5
9 3 2

Thus the cell at ~(3, 2)~ is ~3~ and the cell at ~(1, 2)~ is ~4~.