102711: [AtCoder]ABC271 B - Maintain Multiple Sequences

Problem Statement

There are $N$ sequences of integers.
The $i$-th $(1 \leq i \leq N)$ sequence has $L_i$ terms; the $j$-th $(1 \leq j \leq L_i)$ term of the $i$-th sequence is $a_{i, j}$.

You are given $Q$ queries. For the $k$-th $(1 \leq k \leq Q)$ query, given integers $s_k$ and $t_k$, find the $t_k$-th term of the $s_k$-th sequence.

Constraints

• $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)$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

$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$

Output

Print $Q$ lines. The $k$-th $(1 \leq k \leq Q)$ line should contain the answer to the $k$-th query.

Sample Input 1

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

Sample Output 1

7
5

The $1$-st sequence is $(1, 4, 7)$ and the $2$-nd is $(5, 9)$.
The answer to each query is as follows:

• The $3$-rd term of the $1$-st sequence is $7$.
• The $1$-st term of the $2$-nd sequence is $5$.

Sample Input 2

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

Sample Output 2

128
1
26535
901

问题描述

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

约束条件

• 1≤N，Q≤2×10⁵
• L_i≥1(1≤i≤N)
• ∑i=1NL_i≤2×10⁵
• 1≤a_{i, j}≤10⁹(1≤i≤N, 1≤j≤L_i)
• 1≤s_k≤N，1≤t_k≤L_sk(1≤k≤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≤k≤Q)行应包含第k个查询的答案。

样例输入1

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

样例输出1

7
5

第1个序列是(1, 4, 7)，第2个是(5, 9)。

每个查询的答案如下：

• 第1个序列的第3项是7。
• 第2个序列的第1项是5。

样例输入2

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

样例输出2

128
1
26535
901