Problem Statement

There are $N$ consecutive sections arranged in 1 row, named section $1$, section $2$, $\dots$, section $N$ from left to right. The ground of these $N$ sections is horizontal.

Initially, the height of the wall in every section is $0$.

Perform the following operation in the order $k=1,2, \dots, K$.

• For every integer $i$ satisfying $L_k \leq i \leq R_k$, build a new wall of height $H_k$ and color $C_k$ on top of the wall already built in section $i$ at that point.

For the walls of the $N$ sections after all operations are finished, answer the following $Q$ questions. The $q~(1 \leq q \leq Q)$-th question is given by $2$ integers $I_q, X_q$.

• In section $I_q$, answer the color of the wall at height $(X_q-0.5)$ from the ground. If there is no wall at that height, report that fact.

Walls can be built arbitrarily high, and they never collapse, deform, or change color along the way.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $0 \leq K \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq L_k \leq R_k \leq N$
• $1 \leq C_k \leq 2 \times 10^5$
• $1 \leq H_k \leq 10^9$
• $1 \leq I_q \leq N$
• $1 \leq X_q \leq 2 \times 10^{14}$
• All inputs are integers.

Input

$N$ $K$ $Q$
$L_1$ $R_1$ $C_1$ $H_1$
$\vdots$
$L_K$ $R_K$ $C_K$ $H_K$
$I_1$ $X_1$
$\vdots$
$I_Q$ $X_Q$

Output

The output consists of $Q$ lines. On line $q~(1 \leq q \leq Q)$, print as an integer the color of the wall at height $(X_q-0.5)$ in section $I_q$. If no wall exists at that point, print -1 instead.

Do not forget the newline at the end.

Sample

Sample 1

Input

6 4 3
1 3 1 1
2 4 2 2
4 4 1 3
1 5 5 2
2 3
4 10
5 2

Output

2
-1
5

The walls look as follows.

• The first question asks for the color in section $2$ at height $3-0.5=2.5$ from the ground. The answer is $2$.
• The 2nd question asks for the color in section $4$ at height $10-0.5=9.5$ from the ground, but there is no wall there at all. Therefore, you must print -1.

46 0 1
46 46

-1

200000 5 4
111 1111 1 11111
2 22222 22 2222222
33333 33333 333 333
44 44444 4444 44444444
555 55555 55555 555
66 6666
777 7777
88888 888
99 9999999

22
1
-1
4444