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.