D. Coprime Sums
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a list $$$a = (a_1, \ldots, a_n)$$$ of $$$n$$$ non-negative integers, and you must answer $$$p$$$ queries of the form: given $$$k$$$, print the sum of values of $$$a$$$ at positions that are coprime to $$$k$$$. In other words, return the sum of values of $$$a_i$$$ for those $$$i$$$ such that $$$\text{gcd}(k, i) = 1$$$, where $$$\text{gcd}(k, i)$$$ is the greatest common divisor of $$$k$$$ and $$$i$$$.

Input

The first line of the input contains the number of cases $$$T$$$.

Each case starts with a line of input with two integers $$$n$$$ and $$$p$$$, the size of $$$a$$$ and the number of queries.

The following line of each case contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$.

The next line of each case contains $$$p$$$ integers, the values of $$$k$$$ for each of the queries.

Output

For each case, you must print a line with $$$p$$$ integers, the answers to each of the queries.

Scoring
  1. (13 points) The sum of $$$n$$$ and the sum of $$$p$$$ across all cases are at most $$$10^3$$$.
  2. (24 points) It is guaranteed that $$$a_i$$$ will be non-zero only if $$$i$$$ is prime.
  3. (35 points) $$$k \le 1000$$$, $$$T \le 10$$$, $$$a_i = 1$$$ for all $$$i$$$.
  4. (28 points) No additional restrictions.
Example
Input
3
4 4
1 1 1 1
1 2 3 4
10 4
3 9 2 3 4 5 5 0 2 1
7 1 3 2
8 1
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
1
Output
4 2 3 2 
29 34 25 16 
8000000000
Note
  • $$$1 \le T \le 10^5$$$.
  • $$$1 \le n, p \le 2 \cdot 10^5$$$. The sum of $$$n$$$ and the sum of $$$p$$$ across all cases are at most $$$2 \cdot 10^5$$$.
  • $$$0 \le a_i \le 10^9$$$.
  • $$$k \le n$$$.