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

这是该问题的困难版本。唯一区别在于本版本中 $1 \le q \le 10^5$。仅当该问题的两个版本均被解决时，才允许进行 hack。

存在一个在长度为 $n$ 的数组 $a$ 和长度为 $n-1$ 的数组 $b$ 上进行的过程。

该过程是一系列无限次操作。每次操作如下：

• 首先，随机选择一个整数 $i$（$1 \le i \le n-1$）；
• 然后，同时执行以下赋值（不作任何舍入，因此数值可能变为非整数）：

  $$a_i = \min\left(a_i, \frac{a_i+a_{i+1}-b_i}{2}\right), \quad a_{i+1} = \max\left(a_{i+1}, \frac{a_i+a_{i+1}+b_i}{2}\right).$$

参见“注释”部分以了解一次操作的示例。

可以证明数组 $a$ 是收敛的，即对每个 $i$，极限 $\lim_{t \to \infty} a_i^{(t)}$ 存在。定义函数 $F(a, b)$ 为：在数组 $a$ 和 $b$ 上执行该过程后，$a_1$ 所收敛到的极限值。

你被给定数组 $b$，但未给出数组 $a$。然而，你还被给定第三个数组 $c$。若数组 $a$ 仅包含整数，且对所有 $1 \le i \le n$ 满足 $0 \leq a_i \leq c_i$，则称其为合法数组（good array）。

你的任务是：对 $q$ 个不同的 $x$ 值，分别计算满足 $F(a, b) \geq x$ 的合法数组 $a$ 的个数。由于数组总数可能极大，请将结果对 $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$).

第一行包含一个整数 $n$（$2 \le n \le 100$）。

第二行包含 $n$ 个整数 $c_1, c_2, \ldots, c_n$（$0 \le c_i \le 100$）。

第三行包含 $n-1$ 个整数 $b_1, b_2, \ldots, b_{n-1}$（$0 \le b_i \le 100$）。

第四行包含一个整数 $q$（$1 \le q \le 10^5$）。

第五行包含 $q$ 个用空格分隔的整数 $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$.

输出 $q$ 个整数，其中第 $i$ 个整数是第 $i$ 个查询的答案，即满足 $F(a, b) \geq x_i$ 的好数组 $a$ 的数量对 $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 \gt c_1$;
• $a = [0, -1, 3]$ is not good because $a_2 \lt 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}$.

以下说明假设 $b = [2, 1]$ 且 $c=[2, 3, 4]$（如样例所示）。

不是“好”数组的 $a$ 的示例：

• $a = [3, 2, 3]$ 不是好数组，因为 $a_1 \gt c_1$；
• $a = [0, -1, 3]$ 不是好数组，因为 $a_2 \lt 0$。

一个可能的好数组 $a$ 是 $[0, 2, 4]$。我们可以证明对该数组执行任何操作均无效果，因此 $F(a, b) = a_1 = 0$。

另一个可能的好数组 $a$ 是 $[0, 1, 4]$。在一次以 $i = 1$ 进行的操作中，我们设 $a_1 = \min(\frac{0+1-2}{2}, 0)$ 且 $a_2 = \max(\frac{0+1+2}{2}, 1)$。因此，在一次以 $i = 1$ 进行的操作后，$a$ 变为 $[-\frac{1}{2}, \frac{3}{2}, 4]$。我们可以证明对该数组执行任何操作均无效果，因此 $F(a, b) = -\frac{1}{2}$。