311008: CF1920D. Array Repetition

D. Array Repetitiontime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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

ExampleInput

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

Output

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

Note

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

**题目大意：**

Jayden有一个初始为空的数组`a`。他必须按照给定的顺序执行`n`个操作，操作有两种类型：

1. Jayden将整数`x`（`1 ≤ x ≤ n`）添加到数组`a`的末尾。
2. Jayden将`x`个`a`数组的副本添加到数组`a`的末尾。换句话说，数组`a`变为`[a, a, ..., a]`（`x`个`a`）。保证在此操作之前他已经至少执行了一次第一种类型的操作。

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

**输入数据格式：**

每个测试包含多个测试用例。第一行包含一个整数`t`（`1 ≤ t ≤ 5000`）——测试用例的数量。

每个测试用例的第一行包含两个整数`n`和`q`（`1 ≤ n, q ≤ 10^5`）——操作的数量和查询的数量。

接下来的`n`行描述操作。每行包含两个整数`b`和`x`（`b ∈ {1, 2}`），其中`b`表示操作的类型。如果`b=1`，则`x`（`1 ≤ x ≤ n`）是Jayden添加到数组末尾的整数。如果`b=2`，则`x`（`1 ≤ x ≤ 10^9`）是Jayden添加到数组末尾的副本数量。

每个测试用例的下一行包含`q`个整数`k_1, k_2, ..., k_q`（`1 ≤ k_i ≤ min(10^18, c)`），这些整数表示查询，其中`c`是完成所有`n`个操作后数组的大小。

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

**输出数据格式：**

对于每个测试用例，输出`q`个整数——对Jayden查询的答案。**题目大意：** Jayden有一个初始为空的数组`a`。他必须按照给定的顺序执行`n`个操作，操作有两种类型： 1. Jayden将整数`x`（`1 ≤ x ≤ n`）添加到数组`a`的末尾。 2. Jayden将`x`个`a`数组的副本添加到数组`a`的末尾。换句话说，数组`a`变为`[a, a, ..., a]`（`x`个`a`）。保证在此操作之前他已经至少执行了一次第一种类型的操作。 Jayden有`q`个查询。对于每个查询，你必须告诉他数组`a`的第`k`个元素的值。数组元素从`1`开始编号。 **输入数据格式：** 每个测试包含多个测试用例。第一行包含一个整数`t`（`1 ≤ t ≤ 5000`）——测试用例的数量。 每个测试用例的第一行包含两个整数`n`和`q`（`1 ≤ n, q ≤ 10^5`）——操作的数量和查询的数量。 接下来的`n`行描述操作。每行包含两个整数`b`和`x`（`b ∈ {1, 2}`），其中`b`表示操作的类型。如果`b=1`，则`x`（`1 ≤ x ≤ n`）是Jayden添加到数组末尾的整数。如果`b=2`，则`x`（`1 ≤ x ≤ 10^9`）是Jayden添加到数组末尾的副本数量。 每个测试用例的下一行包含`q`个整数`k_1, k_2, ..., k_q`（`1 ≤ k_i ≤ min(10^18, c)`），这些整数表示查询，其中`c`是完成所有`n`个操作后数组的大小。 保证所有测试用例的`n`和`q`之和不超过`10^5`。 **输出数据格式：** 对于每个测试用例，输出`q`个整数——对Jayden查询的答案。