题目描述

有$N$个整数序列。第$i$个序列$(1 ≤ i ≤ N)$有$L_i$个元素；第$i$个序列的第$j$个元素$(1 ≤ j ≤ L_i)$是$a_i,j$。
现在有$Q$个查询。对于第$k$个查询$(1 ≤ k ≤ Q)$，给定整数$s_k$和$t_k$，请找出第$s_k$个序列的第$t_k$个元素。

输入格式

输入按以下格式从标准输入给出：
$N$ $Q$
$L_1$ $a_{1,1}$ $\cdots$ $a_{1,L_1}$
$\vdots$
$L_N$ $a_{N,1}$ $\cdots$ $a_{N,L_N}$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$

输出格式

输出$Q$行。第$k$行$(1 ≤ k ≤ Q)$应包含第$k$个查询的答案。

样例

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

7
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

样例1解释

第$1$个序列是$(1, 4, 7)$，第$2$个序列是$(5, 9)$。
每个查询的答案如下：

• 第$1$个序列的第$3$个元素是$7$。
• 第$2$个序列的第$1$个元素是$5$。

数据范围

$1 ≤ N, Q ≤ 2 × 10^5$
$L_i ≥ 1 (1 ≤ i ≤ N)$
$\sum_{i=1}^N L_i ≤ 2 × 10^5$
$1 ≤ a_{i,j} ≤ 10^9 (1 ≤ i ≤ N, 1 ≤ j ≤ L_i)$
$1 ≤ s_k ≤ N$
$1 ≤ t_k ≤ L_{s_k} (1 ≤ k ≤ Q)$
所有输入值均为整数。

来源

• AtCoder ABC271B