#P1540C2. Converging Array (Hard Version)

Converging Array (Hard Version)

No submission language available for this problem.

Description

This is the hard version of the problem. The only difference is that in this version $1 \le q \le 10^5$. You can make hacks only if both versions of the problem are solved.

There is a process that takes place on arrays $a$ and $b$ of length $n$ and length $n-1$ respectively.

The process is an infinite sequence of operations. Each operation is as follows:

  • First, choose a random integer $i$ ($1 \le i \le n-1$).
  • Then, simultaneously set $a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right)$ and $a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right)$ without any rounding (so values may become non-integer).
See notes for an example of an operation.

It can be proven that array $a$ converges, i. e. for each $i$ there exists a limit $a_i$ converges to. Let function $F(a, b)$ return the value $a_1$ converges to after a process on $a$ and $b$.

You are given array $b$, but not array $a$. However, you are given a third array $c$. Array $a$ is good if it contains only integers and satisfies $0 \leq a_i \leq c_i$ for $1 \leq i \leq n$.

Your task is to count the number of good arrays $a$ where $F(a, b) \geq x$ for $q$ values of $x$. Since the number of arrays can be very large, print it modulo $10^9+7$.

The first line contains a single integer $n$ ($2 \le n \le 100$).

The second line contains $n$ integers $c_1, c_2 \ldots, c_n$ ($0 \le c_i \le 100$).

The third line contains $n-1$ integers $b_1, b_2, \ldots, b_{n-1}$ ($0 \le b_i \le 100$).

The fourth line contains a single integer $q$ ($1 \le q \le 10^5$).

The fifth line contains $q$ space separated integers $x_1, x_2, \ldots, x_q$ ($-10^5 \le x_i \le 10^5$).

Output $q$ integers, where the $i$-th integer is the answer to the $i$-th query, i. e. the number of good arrays $a$ where $F(a, b) \geq x_i$ modulo $10^9+7$.

Input

The first line contains a single integer $n$ ($2 \le n \le 100$).

The second line contains $n$ integers $c_1, c_2 \ldots, c_n$ ($0 \le c_i \le 100$).

The third line contains $n-1$ integers $b_1, b_2, \ldots, b_{n-1}$ ($0 \le b_i \le 100$).

The fourth line contains a single integer $q$ ($1 \le q \le 10^5$).

The fifth line contains $q$ space separated integers $x_1, x_2, \ldots, x_q$ ($-10^5 \le x_i \le 10^5$).

Output

Output $q$ integers, where the $i$-th integer is the answer to the $i$-th query, i. e. the number of good arrays $a$ where $F(a, b) \geq x_i$ modulo $10^9+7$.

Samples

3
2 3 4
2 1
5
-1 0 1 -100000 100000
56
28
4
60
0

Note

The following explanation assumes $b = [2, 1]$ and $c=[2, 3, 4]$ (as in the sample).

Examples of arrays $a$ that are not good:

  • $a = [3, 2, 3]$ is not good because $a_1 > c_1$;
  • $a = [0, -1, 3]$ is not good because $a_2 < 0$.

One possible good array $a$ is $[0, 2, 4]$. We can show that no operation has any effect on this array, so $F(a, b) = a_1 = 0$.

Another possible good array $a$ is $[0, 1, 4]$. In a single operation with $i = 1$, we set $a_1 = \min(\frac{0+1-2}{2}, 0)$ and $a_2 = \max(\frac{0+1+2}{2}, 1)$. So, after a single operation with $i = 1$, $a$ becomes equal to $[-\frac{1}{2}, \frac{3}{2}, 4]$. We can show that no operation has any effect on this array, so $F(a, b) = -\frac{1}{2}$.