Charlie is writing a mixing software, which takes in an array of records $$$a$$$ with $$$n$$$ elements. Charlie also wants to mix the tracks together. He has devised this clever algorithm (that also produces great soundtracks) called the prefix mixing operation $$$p(a)$$$ as follows:
For example, for the array $$$a = [5,7,10]$$$, the prefix operation would produce $$$p(a) = [5,35,350]$$$, since the multiplication is done in succession. The $$$k$$$-th prefix operation $$$p^{k}$$$ is the prefix operation applied $$$k$$$ times. For example, for $$$k=2$$$, $$$p^{2}(a)$$$ would be defined as $$$p(p(a))$$$, and $$$p^{3}(a) = p(p(p(a)))$$$.
Unfortunately, the current software rendering this transformation takes a long time to run, so Charlie needs your help to fix it. In order to do this, Charlie wants to know arbitrary elements for the array $$$p^{k_i}(a)$$$. Can you help him find them?
The first line contains $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
For each test case, the first line contains two integers $$$n$$$ and $$$q$$$ ($$$1\leq n, q \leq 1000$$$) — the number of elements in the array $$$a$$$ and the number of queries, respectively.
The next line contains $$$n$$$ space-separated integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i\leq 10^9$$$).
The next $$$q$$$ lines each contain two space-separated integers $$$k_i$$$ and $$$x_i$$$ ($$$1\leq k_i\leq 1000, 1\leq x_i\leq n$$$) — which is the $$$i$$$-th query asking for the answer of $$$p^{k_i}(a)[x_i]$$$.
It is guaranteed that the sum of all $$$q$$$ over all test cases is at most $$$1000$$$.
There is no additional bound on the sum of all $$$n$$$ or $$$x_i$$$.
For each query in each test case, output one integer — the value of $$$p^{k_i}(a)[x_i]$$$
25 31 2 3 4 51 11 22 45 45 4 3 2 11 11 21 32 3
1 2 288 5 20 60 6000
For the first test case: $$$p^{1}(a) = [1, 2, 6, 24, 120]$$$ and $$$p^{2}(a) = [1, 2, 12, 288, 34560]$$$
| UTPC Spring 2024 Open Contest |
|---|
| Закончено |
