Polynomial Evaluation

You are given a polynomial of degree (d) with coefficients provided in descending order of powers. Your task is to compute the value of the polynomial for a sequence of integer inputs. In other words, if the polynomial is (P(x) = a_0 x^d + a_1 x^{d-1} + \cdots + a_d), then for each provided value (x), output the value (P(x)).

The input is provided via standard input and the result should be printed to standard output. Use efficient computation methods as the degree or the number of evaluation points may be large.

inputFormat

The input consists of four lines:

1. The first line contains an integer (d) representing the degree of the polynomial.
2. The second line contains (d+1) space-separated integers, which are the coefficients (a_0, a_1, \ldots, a_d) in descending order of powers. That is, (a_0) is the coefficient of (x^d) and (a_d) is the constant term.
3. The third line contains an integer (n) representing the number of x-values.
4. The fourth line contains (n) space-separated integers representing the x-values for which the polynomial must be evaluated.

outputFormat

Output a single line containing (n) space-separated integers. Each integer is the polynomial value at the corresponding x-value from the input.## sample

2
1 -3 2
3
1 2 3

0 0 2