当前没有测试数据。

B - 维护多个序列

分数：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