C2. Converging Array (Hard Version)time limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputThis 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.InputThe 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).OutputOutput 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.ExampleInput
3
2 3 4
2 1
5
-1 0 1 -100000 100000
Output
56
28
4
60
0
NoteThe 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}.
3
2 3 4
2 1
5
-1 0 1 -100000 100000

56 28 4 60 0 
['dp', 'math', '*2900']