CF1540C2.Converging Array (Hard Version)

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$ .

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}$ .