K. NTT
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a polynomial of degree $$$n$$$, $$$F(x)=f_0+f_1x+f_2x^2+ \dots +f_nx^n$$$, and a prime number $$$p$$$.

Then there are $$$q$$$ queries. In each query, an integer $$$x_i$$$ is given, and you need to find the value of $$$F(x_i) \bmod p$$$$$$^{\text{∗}}$$$.

$$$^{\text{∗}}$$$It can be proved that there is a unique integer $$$r$$$ such that $$$0 \leq r \lt p$$$ and $$$F(x_i) \equiv r \pmod p$$$, and $$$r$$$ is exactly the number you need to output.

Input

Each test file contains multiple test cases. The first line contains an integer $$$T (1 \leq T \leq 100)$$$, the number of test cases.

For each test case, the first line contains three integers $$$n,p,q$$$ $$$(1 \leq n \leq 10^6,$$$ $$$2 \leq p \lt 5 \times 10^3,$$$ $$$1 \leq q \leq 5 \times 10^3)$$$, denoting the degree of polynomial $$$F(x)$$$, the given prime number, and the number of queries.

The second line contains $$$n+1$$$ integers, representing the coefficients $$$f_i$$$ of $$$F(x)$$$ from low degree to high degree $$$(0 \leq f_i \leq 10^6)$$$.

The next $$$q$$$ lines each contain one integer $$$x_i$$$ $$$(|x_i| \leq 10^6)$$$, and you need to find the value of $$$F(x_i) \bmod p$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, and the sum of $$$q$$$ does not exceed $$$5 \times 10^3$$$.

Output

For each query, output one line containing one integer, the value of $$$F(x_i) \bmod p$$$.

Example
Input
2
3 5 3
0 9 0 6
-5
-7
-10
3 7 3
8 0 2 4
1
9
-10
Output
0
4
0
0
6
2
Note

For the second query of the first test case in the sample:

$$$F(x)=9x+6x^3$$$

$$$F(-7)=9\times(-7)+6\times (-7)^3=-2121 \equiv 4 \pmod 5$$$