Problem Statement

There is an integer $X$. The initial value of $X$ is $0$. You are also given a sequence $A_0,A_1,\cdots,A_{N-1}$ of length $N$.
From now on, the following operation will be performed repeatedly.

Operation: Compute the remainder of $X$ divided by $N$, and let it be $r$. Add $A_r$ to $X$.

There are $Q$ queries. In each query, a positive integer $K$ is given, so find the value of $X$ after the $K$-th operation.

Input

$N$
$A_0 \ A_1 \ \cdots \ A_{N-1}$
$Q$
$K_1$
$K_2$
$\vdots$
$K_Q$

The input satisfies the following constraints.

• All input values are integers
• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^6 (0 \leq i < N)$
• $1 \leq Q \leq 10^5$
• $1 \leq K_i \leq 10^{12} (1 \leq i \leq Q)$

Output

Output $Q$ lines.
On the $i (1 \leq i \leq Q)$-th line, output the value of $X$ after the $K_i$-th operation.

Sample

5
3 3 2 4 7
2
2
4

7
16

2
314159 141421
1
271828

61919700120