Problem: 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: 

  * First, choose a random integer i (1 ≤ i ≤ 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 ≤ a_i ≤ c_i for 1 ≤ i ≤ n.

Your task is to count the number of good arrays a where F(a, b) ≥ 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 ≤ n ≤ 100).

The second line contains n integers c_1, c_2 …, c_n (0 ≤ c_i ≤ 100).

The third line contains n-1 integers b_1, b_2, …, 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, …, x_q (-10^5 ≤ x_i ≤ 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) ≥ x_i modulo 10^9+7.

Example

Input


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


Output


56
28
4
60
0

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((0+1-2)/(2), 0) and a_2 = max((0+1+2)/(2), 1). So, after a single operation with i = 1, a becomes equal to [-1/2, 3/2, 4]. We can show that no operation has any effect on this array, so F(a, b) = -1/2.

Solution (in CPP):

Solution:
/*
Idea:
Looking in original statement's perspective is very difficult.
Let's look at what the operation do to other things (try anything you can come up with)

Attempt #1:
Look at the difference of consecutive elements in A
Useful Information:
- The operation makes the pair of consecutive (i, i+1) that differs less than b_i into differ exactly b_i
- It borrow some 'differences' from their consecutive pairs (half from left, half from right)

However, it stucked real fast and I can't come up with any feasible idea

Attempt #2:
Use the information from previous attempt,
try convert array A and convert the operation so that when the operation occurs at (i,i+1),
the element a_i and a_{i+1} will become the same (i.e. maybe averge them)

This is guessed by experience.

We will convert from 
[a_1, a_2, ..., a_n]
into 
[a_1, a_2-b_1, a_3-b_1-b_2, ..., a_n-b_1-b_2-...-b_{n-1}]

That is, we convert 'a_i' into 'a_i - sum(b_j)' (for 1<=j<i)
Let's call it 'A_i'

Now, let's look when the operation will affect (i,i+1)
a_{i+1} - a_i < b_i
a_{i+1} - b_i < a_i
(a_{i+1} - b_1 - b_2 - ... - b_i) < (a_i - b_1 - b_2 - ... - b_{i-1})
A_{i+1} < A_i

The operation will affect (i,i+1) when A_{i+1} < A_i

How will the operation affect our new array ?
A[i] becomes (a[i]+a[i+1]-b[i])/2 - sum(b[j])
= ( (a[i+1]-b[1]-b[2]-...-b[i])+(a[i]-b[1]-...-b[i-1]) )/2
= (A[i+1]+A[i])/2

A[i+1] also becomes (A[i+1]+A[i])/2

Hence, they just become the same value, without interfering other values at all

After this is just some lots of visualization and thinking how the setting of A affect the final A[1], etc.

One last bit to get the hard version:
I was a bit too persimissm that the worst case of all is -5050,
and the best case is 100,
then there would be 5151 cases to calculate.

That's true,
but if I had looked into a little more precisely,
for each setting of C[1...n] and B[1...n-1],
There is at most 100 cases we need to evaluate.

and I wouldn't have to look at the hint ;_;

*/

#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define ROF(i,a,b) for(int i=(a); i>=(b); --i)
#define pb push_back
#define eb emplace_back
#define SZ(a) (int)(a).size()
#define all(a) (a).begin(), (a).end()
#define make_unique(a) sort(all((a))), (a).erase(unique(all((a))),(a).end())
#define x first
#define y second
#define MP make_pair
#define MT make_tuple
#define debug(x) cout << #x << " = " << x << endl
#define debug2(x,y) FOR(i,1,y) cout << "##"; cout << #x << " = " << x << endl
#define mset(x,y) memset((x), (y), sizeof(x))

using namespace std;

typedef long long i64;
typedef long double ld;
typedef tuple<int,int,int> iii;
typedef pair<int,int> pii;
typedef pair<i64,i64> pll;
typedef vector<int> vi;
typedef vector<i64> vl;
typedef vector<vector<int>> vvi;
typedef vector<vector<i64>> vvl;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<i64,i64>> vpll;

int readInt(){ int a; scanf("%d",&a); return a; }
i64 readLong(){ i64 a; scanf("%lld",&a); return a;}
void readString(char *s){ scanf(" %s",s); }

string print(int a){ return to_string(a); }
string print(i64 a){ return to_string(a); }
string print(string a){ return a; }
template<typename T1, typename T2> string print(pair<T1,T2> x){ return "("+print(x.x)+","+print(x.y)+")"; }
template<typename T> string print(vector<T> v){ string ans = "[ "; for(T e : v) ans += print(e)+" "; ans += "]"; return ans; }
template<typename T> string print(T *a, T *b){ string ans = "[ "; while(a!=b) ans += print(*(a++))+" "; ans += "]"; return ans; }

const int mod = 1000000007;
int add(int a, int b){ return ((a+=b)>=mod)?a-mod:a; }
int mul(int a, int b){ return a*1ll*b%mod; }
void adding(int &a, int b){ a = add(a, b); }
int pw(int a, int b){
	if(a==0) return 0;
	int ans = 1, res = a;
	for(int i = 1; i <= b; i<<=1, res=mul(res,res)){
		if(i&b) ans = mul(ans,res);
	}
	return ans;
}

const int N = 105;
int dp[N][N*N];
int C[N], B[N];
int ans[N];

int main(){
	int n = readInt();
	FOR(i, 1, n) C[i]=readInt();
	int sum = 0;
	FOR(i, 1, n-1){
		B[i]=readInt();
		sum += B[i];
		B[i] = B[i-1]+sum;
	}
	int worst = (-B[n-1]-n+1)/n;
	int csum = accumulate(C+1,C+1+n,0);
	int best = (csum-B[n-1])/n;
	FOR(x, worst, best){
		mset(dp, 0);
		FOR(i, 0, csum) dp[0][i] = 1;
		FOR(i, 1, n){
			FOR(j, max(0,B[i-1]+x*i), csum){
				adding(dp[i][j], dp[i-1][j]);
				if(j-C[i]>0) adding(dp[i][j], mod-dp[i-1][j-C[i]-1]);
				if(j>0) adding(dp[i][j], dp[i][j-1]);
			}
		}
		ans[x-worst] = dp[n][csum];
	}
	int q = readInt();
	while(q--){
		int x = readInt();
		if(x > best) printf("0\n");
		else printf("%d\n",ans[max(x-worst,0)]);
	}
	return 0;
}