問題文

$N$ 個の連続する区画が1列に並んでおり, これらは左から順に区画 $1$, 区画 $2$, $\dots$, 区画 $N$ と名付けられている. また, この $N$ 個の区画の地面は水平である.

最初, 全ての区画の壁の高さは $0$ である.

$k=1,2, \dots, K$ の順に以下の操作を行う.

• $L_k \leq i \leq R_k$ を満たす全ての整数 $i$ に対して, 区画 $i$ にその時点で建てられている壁の上に新たに高さ $H_k$, 色 $C_k$ の壁を建てる.

全ての操作を終えた $N$ 個の区画の壁に対して, 次の $Q$ 個の質問に答えよ. ただし, $q~(1 \leq q \leq Q)$ 番目の質問は $2$ つの整数 $I_q, X_q$ で与えられる.

• 区画 $I_q$ において, 地面から高さ $(X_q-0.5)$ 地点の壁の色を答えよ. ただし, その高さに壁がない場合はその旨を報告せよ.

なお, 壁はいくらでも高く建てることができるものとし, 途中で壁が崩落したり, 変形, 変色しないものとする.

制約

• $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}$
• 入力は全て整数である.

入力

$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$

出力

出力は $Q$ 行からなる. 第 $q~(1 \leq q \leq Q)$ 行目には, 区画 $I_q$ にある高さ $(X_q-0.5)$ 地点の壁の色を整数で答えよ. ただし, その地点に壁が存在しない場合は代わりに -1を出力せよ.

最後に改行を忘れないこと.

サンプル

サンプル1

入力サンプルをコピー

入力

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

出力

2
-1
5

壁の状況は以下のようになっている.

• 最初の質問は区画 $2$ における地面から高さ $3-0.5=2.5$ 地点の色である. これは $2$ が答えである.
• 2番目の質問は区画 $4$ における地面から高さ $10-0.5=9.5$ 地点の色であるが, そもそもそこに壁はない. よって, -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