Sharky is a hungry shark with a penchant for tuna. In the ocean, there are $n$ spots that he considers tuna-rich , where the $i$-th spot contains $a_i$ tunas initially for each integer $1 \le i \le n$. Each day, Sharky goes to every tuna-rich spot and consumes tunas. In a tuna-rich spot with $x$ tunas remaining, Sharky consumes $\lfloor \sqrt{x}\rfloor$ tunas (the square-root of $x$, rounded down to the nearest integer). Note that the tunas do not regenerate.

Being a shark that cares about his food supply, Sharky has $q$ questions. The $j$-th question asks about the total number of tunas left in the tuna-rich spots after $d_j$ days. However, he is too busy eating tunas to answer his own questions. Hence, Sharky asks you, a smart person, to answer his questions. As the total number of tunas may be too large, he would like you to output your answers modulo $10^9+7$.

Input

The first line contains a positive integer $n$, denoting the number of tuna rich spots.

The second line contains $n$ non-negative integers, $a_1$, $a_2$, $\ldots$, $a_n$, where $a_i$ denotes the number of tunas in the $i$-th tuna rich spot.

The third line contains a positive integer $q$, denoting the number of questions that Sharky asks.

The fourth line contains $q$ non-negative integers, $d_1$, $d_2$, $\ldots$, $d_q$, where $d_j$ denotes Sharky's $j$-th question.

Output

Output $q$ integers separated by spaces, the $j$-th being the total number of tunas left in the tuna rich spots, modulo $10^9+7$.

Constraints

For all test cases, $1\le n,q\le 3\times 10^5$, $0\le a_i\le 10^{18}$ for all $1\le i\le n$, $0 \le d_j \le 10^{18}$ for all $1\le j\le q$.

Subtask 1 (12 points): $n\le 1000$, $d_j\le 1000$ for all $1 \le j \le q$.

Subtask 2 (13 points): $n=1$, $a_1$ is a perfect square.

Subtask 3 (21 points): $a_i$ is a perfect square for all $1\le i\le n$.

Subtask 4 (16 points): $a_i\le 10000$ for all $1\le i\le n$.

Subtask 5 (15 points): $n=1$.

Subtask 6 (23 points): No additional constraints.