B'This is the hard version of the problem. The only difference is that in this version 1 <= q <= 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: 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 <= q a_i <= q c_i for 1 <= q i <= q 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 <= n <= 100 ). The second line contains n integers c_1, c_2 ldots, c_n ( 0 <= c_i <= 100 ). The third line contains n-1 integers b_1, b_2, ldots, b_{n-1} ( 0 <= b_i <= 100 ). The fourth line contains a single integer q ( 1 <= q <= 10^5 ). The fifth line contains q space separated integers x_1, x_2, ldots, x_q ( -10^5 <= x_i <= 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: 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]$$'...