問題
山本君は辛いものが大好きですが、甘いものは嫌いです。あなたはそんな山本君からの質問に答えてあげることにしました。
$N$ 個の果物があります。$i$ $(1 \leq i \leq N)$ 番目の果物の辛さは $a_i$ 甘さは $b_i$ です。
以下のような $Q$ 個の質問に答えて下さい。
- $j$ $(1 \leq j \leq Q)$ 番目の質問： $1$ 番目から $k_j$ 番目までの果物の中で辛さが $x_j$ 以上の果物のうち、甘さが最小である果物の甘さはいくつか
入力
$N$ $a_1$ $b_1$ $a_2$ $b_2$ $\vdots$ $a_N$ $b_N$ $Q$ $k_1$ $x_1$ $k_2$ $x_2$ $\vdots$ $k_Q$ $x_Q$
出力
出力は $Q$ 行からなる。
$j$ 行目には $j$ 番目の質問の答えを出力せよ。また、各出力の末尾には改行を入れること。
制約
- $1 \leq N,Q \leq 2 \times 10^5$
- $-10^{18} \leq a_i,b_i \leq 10^{18}$
- $1 \leq k_j \leq N$
- $-10^{18} \leq x_j \leq \max(a_1,a_2,\ldots,a_{k_j})$
入出力例
入力例１
5 1 8 2 5 -3 7 4 1 9 -10 3 3 1 5 0 1 -100
出力例１
5 -10 8
$1$ つ目の質問について考えます。
$1$ 番目から $3$ 番目までの果物のうち辛さが $1$ 以上であるものは $1$ 番目と $2$ 番目の果物です。そのうち甘さが最小の果物は $2$ 番目の果物であるため、その甘さである $5$ を出力します。
入力例２
5 100 100 100 100 100 100 100 100 100 100 7 5 84 2 -61 2 -100 3 -94 1 -36 2 4 3 100
出力例２
100 100 100 100 100 100 100
入力例３
13 -564834199966848102 272451714939029125 698676252940567988 882057172560612685 -44757501653010397 664061199400777125 -990661981426965995 332980716801178345 10820549165623655 -904081683787680750 996942982171460025 120317228735897817 -387039200867417522 390286403846989153 -234269582359589314 972714814181653863 -535139325958298787 -804258393236661777 -632910042371720320 604804434309365147 -327569833280921361 -638153548645516090 550038636786166635 542785298551791551 596187630928812092 -803621689288618772 18 6 450560451240628400 5 -274709076466188390 9 334761327934549054 12 400525925286552188 10 -183235214278307869 9 836467438300099814 1 -820126762478344744 13 263757037714952926 10 -658170521247447451 12 44315375656790473 9 -478803351108509481 4 -391325322965573960 11 399928387174378445 13 -257337221927419505 10 517434576300890772 1 -604766235523101261 2 3896746287429035 5 -258615370869136842
出力例３
120317228735897817 -904081683787680750 120317228735897817 120317228735897817 -904081683787680750 120317228735897817 272451714939029125 -803621689288618772 -904081683787680750 120317228735897817 -904081683787680750 664061199400777125 120317228735897817 -904081683787680750 120317228735897817 272451714939029125 882057172560612685 -904081683787680750