维护多个序列

题目描述

有 $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$ 项。

输入格式

输入按以下格式从标准输入给出:

$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

数据范围

• $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)$
• 输入中的所有值均为整数。