Converging Array (Hard Version)

5000ms

262144K

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

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

Sample Input:

3
2 3 4
2 1
5
-1 0 1 -100000 100000

Sample Output:

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

Informação

Provedor Codeforces

Código CF1540C2