← 返回题目列表

Codeforces · 1920/D

D. 数组重复

中文机器翻译题面 查看原题

Jayden 有一个数组 $$$a$$$ 最初是空的。他必须按照给定的顺序执行两种类型的 $$$n$$$ 操作。

1. Jayden 将一个整数 $$$x$$$ ($$$1 \leq x \leq n$$$) 附加到数组 $$$a$$$ 的末尾。
2. Jayden 将数组 $$$a$$$ 的 $$$x$$$ 副本附加到数组 $$$a$$$ 的末尾。换句话说,数组 $$$a$$$ 变为 $$$[a,\underbrace{a,\ldots,a}_{x}]$$$。保证在此之前他至少已经做过一次第一类操作。

Jayden 有 $$$q$$$ 查询。对于每个查询,您必须告诉他数组 $$$a$$$ 的第 $$$k$$$ 个元素。数组的元素从$$$1$$$开始编号。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 5000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \leq n, q \leq 10^5$$$) — 操作数和查询数。

以下 $$$n$$$ 行描述了操作。每行包含两个整数 $$$b$$$ 和 $$$x$$$ ($$$b \in \{1, 2\}$$$),其中 $$$b$$$ 表示操作类型。如果 $$$b=1$$$,则 $$$x$$$ ($$$1 \leq x \leq n$$$) 是 Jayden 追加到数组末尾的整数。如果 $$$b=2$$$,则 $$$x$$$ ($$$1 \leq x \leq 10^9$$$) 是 Jayden 追加到数组末尾的副本数。

每个测试用例的下一行包含 $$$q$$$ 整数 $$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq \min(10^{18}, c)$$$),表示查询,其中 $$$c$$$ 是完成所有 $$$n$$$ 操作后数组的大小。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出 $$$q$$$ 整数 - Jayden 查询的答案。

示例

输入 #1

4
5 10
1 1
1 2
2 1
1 3
2 3
1 2 3 4 5 6 14 15 16 20
10 10
1 3
1 8
2 15
1 6
1 9
1 1
2 6
1 1
2 12
2 10
32752 25178 3198 3199 2460 2461 31450 33260 9016 4996
12 5
1 6
1 11
2 392130334
1 4
2 744811750
1 10
1 5
2 209373780
2 178928984
1 3
2 658326464
2 1000000000
914576963034536490 640707385283752918 636773368365261971 584126563607944922 1000000000000000000
2 2
1 1
1 2
1 2

输出 #1

1 2 1 2 3 1 2 3 1 3
9 8 1 3 1 3 6 3 8 8
11 11 11 10 11
1 2

注意

在第一个测试用例中:

- 第一次操作后 $$$a = [1]$$$;
- 第二次操作后 $$$a = [1, 2]$$$;
- 第三次操作后 $$$a = [1, 2, 1, 2]$$$;
- 第四次操作后 $$$a = [1, 2, 1, 2, 3]$$$;
- 第五次操作后 $$$a = [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3]$$$。

在第四个测试用例中,所有操作 $$$a = [1, 2]$$$ 后。