配点 : $200$ 点

問題文

整数からなる数列が $N$ 個あります。 $i \, (1 \leq i \leq N)$ 番目の数列は $L_i$ 項からなり、$i$ 番目の数列の第 $j \, (1 \leq j \leq L_i)$ 項 は $a_{i, j}$ です。

$Q$ 個のクエリが与えられます。$k \, (1 \leq k \leq Q)$ 番目のクエリでは、整数 $s_k, t_k$ が与えられるので、$s_k$ 番目の数列の第 $t_k$ 項を求めてください。

制約

• $1 \leq N, Q \leq 2 \times 10^5$
• $L_i \geq 1 \, (1 \leq i \leq N)$
• $\sum_{i=1}^N L_i \leq 2 \times 10^5$
• $1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)$
• $1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$N$ $Q$

$L_1$ $a_{1, 1}$ $\ldots$ $a_{1, L_1}$

$\vdots$

$L_N$ $a_{N, 1}$ $\ldots$ $a_{N, L_N}$

$s_1$ $t_1$

$\vdots$

$s_Q$ $t_Q$

出力

$Q$ 行出力せよ。$k \, (1 \leq k \leq Q)$ 行目には、$k$ 番目のクエリに対する答えを出力せよ。

2 2
3 1 4 7
2 5 9
1 3
2 1

7
5

$1$ 番目の数列は $(1, 4, 7)$、$2$ 番目の数列は $(5, 9)$ です。 それぞれのクエリに対する答えは次のようになります。

• $1$ 番目の数列の第 $3$ 項は $7$ です。
• $2$ 番目の数列の第 $1$ 項は $5$ です。

3 4
4 128 741 239 901
2 1 1
3 314 159 26535
1 1
2 2
3 3
1 4

128
1
26535
901