Your task consists of evaluate a polynomial of degree n (0 <= n <= 999) represented by its n+1 coefficients of the form:

in each one of the k (1 <= k <= 100) points x₁, x₂, …, x_k. The coefficients of the polynomial and the values where they will be evaluated are integers in the interval [-100, 100] that guarantees that the polynomial's evaluation is at the most 2⁶³ – 1.

Input

There will be multiple test cases, each one with 4 lines that are described below
n: degree of polynomial.

c_n c_n-1 … c₂ c₁ c₀: coefficients of the polynomial separated by a single space.

k: number of points to evaluate the polynomial.

x₁ x₂ … x_k-1 x_k: points to evaluate the polynomial separated by a single space.

The final test case is a single line where n = -1 and this case should not be processed.

Output

For each test case you should print k + 1 lines of output, the very first line containing the case number and the following k lines with the result of the polynomial's evaluation in each one of the k given points. See the sample.

Example

Input:
2
1 -2 -1
5
0 1 -1 2 -2
3
2 1 -2 -1
4
0 -1 2 -2
-1

Output:
Case 1:
-1
-2
2
-1
7
Case 2:
-1
0
15
-9