Modulo

Aubichol Internship Test
Limits 4s, 512 MB

Let's get straight into the problem. In ths problem, here will be multiple test cases. In each test case you will be given an array $A$ of $N$ integers. Then there will be $Q$ queries. In each query You will be given an integer $M$. For every $i$ where $1 \le i \le N$ you have to change $A[i]$ to $A[i]$ mod $M$. After executing all queries you have to print the array $A$ in the order of input.

Note that you have to execute $Q$ queries in the order of input.

Input

Input will start with a single integer $T$ ($1 \le T \le 10^5$), denoting the number of test cases.

For each test case, the first line will contain an integer $N$ ($1 \le N \le 10^5$). $N$ is the size of the array $A$.

Second-line will contain $N$ space-separated integers in the range $[1, 2^{60}]$.

Third line will contain an integer $Q$ ($1 ≤ Q ≤ 10^5$). $Q$ is the number of queries. Fourth line will contain $Q$ integers in the range $[1, 2^{61}]$. Each of the $Q$ integers are the $M$ explained in the statement.

It is guaranteed that sum of total $N$ over all test cases doesn't exceed 500000 and the sum of total $Q$ over all test cases doesn't exceed 500000.

Output

For each test case print "Case x:" in a line without quotations where x is the test case number.

Then print the elements of array $A$ separated by spaces. See sample input-output for better understanding.

Sample

InputOutput
2
2
4 4
1
2
3
8 4 8
1
2

Case 1:
0 0
Case 2:
0 0 0