Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.

You are given a polynomial of degree N with integer coefficients. Your task is to find the value of this polynomial at some K different integers, modulo 786433.

------ Input ------

The first line of the input contains an integer N denoting the degree of the polynomial.
The following line of each test case contains (N+1) integers denoting the coefficients of the polynomial. The i^{th} numbers in this line denotes the coefficient a_{i-1} in the polynomial a_{0} + a_{1} × x^{1} + a_{2} × x^{2} + ... + a_{N} × x^{N}.
The following line contains a single integer Q denoting the number of queries.
The j^{th} of the following Q lines contains an integer number x_{j} denoting the query.

------ Output ------

For each query, output a single line containing the answer to the corresponding query. In other words, the j^{th} line of the output should have an integer equal to a_{0} + a_{1} × x_{j} + a_{2} × x_{j}^{2} + ... + a_{N} × x_{j}^{N} modulo 786433.

------ Constraints -----

$0 ≤ a_{i}, x_{j} < 786433$
$Subtask #1 (37 points): 0 ≤ N, Q ≤ 1000$
$Subtask #2 (63 points): 0 ≤ N, Q ≤ 2.5 × 10^{5}$

------ Example ------

Input:
2
1 2 3
3
7
8
9

Output:
162
209
262

------ Explanation ------

Example case 1.

$Query 1: 1 + 2 × 7 + 3 × 7 × 7 = 162$
$Query 2: 1 + 2 × 8 + 3 × 8 × 8 = 209$
$Query 3: 1 + 2 × 9 + 3 × 9 × 9 = 262$

见题面

见题面