D. Array Repetition
binary search; brute force; dsu; implementation; math
Jayden has an array \(a\) which is initially empty. There are \(n\) operations of two types he must perform in the given order. Jayden appends an integer \(x\) (\(1 \leq x \leq n\)) to the end of array \(a\). 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\).
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\).
For each test case, output \(q\) integers — answers to Jayden's queries.
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]\).