CF1920D.Array Repetition

Jayden has an array $a$ which is initially empty. There are $n$ operations of two types he must perform in the given order.

1. Jayden appends an integer $x$ ($1 \leq x \leq n$) to the end of array $a$.
2. Jayden appends $x$ copies of array $a$ to the end of array $a$. In other words, array $a$ becomes $[a,\underbrace{a,\ldots,a}_{x}]$. It is guaranteed that he has done at least one operation of the first type before this.

Jayden has $q$ queries. For each query, you must tell him the $k$-th element of array $a$. The elements of the array are numbered from $1$.

杰登有一个初始为空的数组 $a$。他必须按给定顺序执行 $n$ 个操作，操作分为两类：

1. 杰登将一个整数 $x$（$1 \leq x \leq n$）追加到数组 $a$ 的末尾；
2. 杰登将 $x$ 份当前数组 $a$ 追加到 $a$ 的末尾。换言之，数组 $a$ 变为 $[a,\underbrace{a,\ldots,a}_{x}]$。保证在执行该操作前，至少已执行过一次第一类操作。

杰登有 $q$ 个查询。对每个查询，你需要告诉他数组 $a$ 的第 $k$ 个元素（数组元素编号从 $1$ 开始）。

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5000$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1 \leq n, q \leq 10^5$) — the number of operations and the number of queries.

The following $n$ lines describe the operations. Each line contains two integers $b$ and $x$ ($b \in {1, 2}$), where $b$ denotes the type of operation. If $b=1$, then $x$ ($1 \leq x \leq n$) is the integer Jayden appends to the end of the array. If $b=2$, then $x$ ($1 \leq x \leq 10^9$) is the number of copies Jayden appends to the end of the array.

The next line of each test case contains $q$ integers $k_1, k_2, \ldots, k_q$ ($1 \leq k_i \leq \min(10^{18}, c)$), which denote the queries, where $c$ is the size of the array after finishing all $n$ operations.

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含一个整数 $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$。

For each test case, output $q$ integers — answers to Jayden's queries.

对于每个测试用例，输出 $q$ 个整数——即 Jayden 各个查询的答案。

In the first test case:

• After the first operation $a = [1]$;
• After the second operation $a = [1, 2]$;
• After the third operation $a = [1, 2, 1, 2]$;
• After the fourth operation $a = [1, 2, 1, 2, 3]$;
• After the fifth operation $a = [1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3, 1, 2, 1, 2, 3]$.

In the fourth test case, after all operations $a = [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]$。