题目描述

有 $N$ 条整数数列，第 $i$ 条长度为 $L_i$。每次查询给出 $s$、$t$，请输出第 $s$ 条数列的第 $t$ 个数，编号从 1 开始。

输入格式

第一行 $N$、$Q$；接下来 $N$ 行，每行先给出 $L_i$，再给出该行的 $L_i$ 个整数；随后 $Q$ 行，每行两个整数 $s$、$t$。

输出格式

每次查询的答案单独输出一行。

数据范围

$1 \le N,Q \le 2 \times 10^{5}$；$L_i \ge 1$；$\sum_{i=1}^{N} L_i \le 2 \times 10^{5}$；数列元素在 $[1,10^{9}]$；$1 \le s \le N$；$1 \le t \le L_s$。所有输入值均为整数。

输入输出样例

样例 1

1 1
1 1
1 1

1

样例 2

1 2
2 1 1000000000
1 1
1 2

1
1000000000

样例 3

3 3
1 3
1 5
1 8
3 1
1 1
2 1

8
3
5

样例 4

3 5
3 6 2 9
1 4
2 7 8
1 1
1 3
2 1
3 1
3 2

6
9
4
7
8

样例 5

2 3
2 11 11
1 11
1 2
1 2
2 1

11
11
11

样例 6

3 4
2 1 2
3 3 4 5
4 6 7 8 9
1 2
2 2
3 2
3 4

2
4
7
9

样例 7

3 5
1 1000000000
4 1 2 3 4
2 999999999 1
3 2
2 4
1 1
3 1
2 1

1
4
1000000000
999999999
1