Description:
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 Format:
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 Format:
For each test case, output $$$q$$$ integers — answers to Jayden's queries.
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]$$$.