F. Modular Madness
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Tingyun gives you an array $$$a$$$ of size $$$n$$$.

Given an integer $$$x$$$, define functions $$$f_0(x),f_1(x),\ldots,f_n(x)$$$ as follows:

  1. $$$f_0(x)=x$$$
  2. $$$f_k(x)=f_{k-1}(x) \text{ mod } a_k$$$ for any integer $$$k \gt 0$$$.

In other words, $$$f_n(x) = (\ldots((x \text{ mod } a_1)\text{ mod } a_2)\ldots \text{ mod } a_n)$$$.

Note for positive integers $$$a$$$ and $$$b$$$, $$$a \text{ mod } b$$$ is the unique integer $$$0\leq c \lt b$$$ such that $$$a-c$$$ is divisible by $$$b$$$. For example, $$$5 \text{ mod } 3 = 2$$$.

Tingyun then gives you $$$q$$$ values of $$$x$$$. For each $$$x$$$, please output the value of $$$f_n(x)$$$.

Input

The first line contains an integer $$$t$$$ – the number of test cases ($$$1 \leq t \leq 10^4$$$).

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

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).

The next $$$q$$$ lines each contain an integer $$$x$$$ ($$$1 \leq x \leq 10^9$$$).

It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$q$$$ exceeds $$$10^5$$$ over all test cases.

Scoring

Partial credits will be given to programs who pass tests with smaller constraints outlined below.

GroupPointsConstraints
120$$$q=1$$$
240$$$a_i, x \leq 50$$$, sum of $$$q\leq 3\cdot 10^4$$$
340No further constraints
Output

Output the answer for each $$$x$$$ on a new line.

Example
Input
2
3 3
15 13 11
2145
2146
25
5 6
14182 5527 2319 958 724
819248982
912849157
8172857
871267639
126471891
918273752
Output
0
1
10
516
380
24
486
108
157