You have to generate an array of N numbers.
The first element of the array is 0. You are given an additive factor k.
The $i^{th}$ element of the array is k plus the sum of all the elements till $(i-1)^{th}$ index ($2 \le i \le N$).

You are given Q questions. In each question, you are given a number S.
You want to generate a number P closest to S such that $P \le S$ . P is the sum of some array elements (an array element can be used atmost once).
For each question, you have to find the minimum difference between S and P.

Input format

• The first line contains an integer T (the number of test cases).

• The first line of each test case contains 3 space-separated integers N, k and Q.

• Then Q lines follow and each line has an integer S.

Output format

For each test case, output Q space-separated integers, $i^{th}$ integer being the answer to $i^{th}$ question.
Answer for each test case should come in a new line.

Constraints

$1 \le T \le 100$

$0 \le N \le 1000$

$1 \le Q \le 1000$

$1 \le k,S \le 10^ 9$