#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define per(i,a,b) for(i=(a);i>=(b);--i)
#define REP(i,a,b) for(i=(a);i< (b);++i)
#define PER(i,a,b) for(i=(a);i> (b);--i)
#define ERR(...) fprintf(stderr,__VA_ARGS__)
template<class T>inline void cmn(T &x,const T &a){if(a<x)x=a;}
template<class T>inline void cmx(T &x,const T &a){if(x<a)x=a;}
template<class T>inline bool bmn(T &x,const T &a){if(a<x){x=a;return true;}else return false;}
template<class T>inline bool bmx(T &x,const T &a){if(x<a){x=a;return true;}else return false;}

//Fast IO libs.
//This fast IO lib occupies the stdin once a read operation is performed.
namespace IO{
	//Input buffer size. 
	const int l=1<<20;
	//Output buffer size. 
	const int lo=21;
	char buf[l],*s,*t,c;bool f;
	inline void gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			c=s==t?EOF:*s++;
		}else c=*s++;
	}
	//gi(x): Get an integer from stdin and write it to x.
	template<class I>inline void gi(I &x){
		x=0;f=false;gc();while(c<'0'||c>'9'){if(c=='-')f=true;gc();}
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}if(f)x=-x;
	}
	//giu(x): Get a non-positive integer from stdin and write it to x.
	template<class I>inline void giu(I &x){
		x=0;f=false;gc();while(c<'0'||c>'9')gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}if(f)x=-x;
	}
	//gs(x): Get a string from stdin and write the string length to n.
	inline void gs(char *S,int &n){
		n=0;
		gc();while(!isgraph(c))gc();while(isgraph(c)){S[n++]=c;gc();}
	}
	//gch(x): Get a char from stdin.
	inline void gch(char &s){
		gc();while(!isgraph(c))gc();s=c;
	}
	char buf0[lo];int a;
	//pi(x): Put an integer x to stdout.
	//Require: |IntToString(x)| < lo.
	template<class I>inline void pi(I x){
		if(x<0){putchar('-');x=-x;}
		do buf0[++a]=(char(x%10)^'0');while(x/=10);
		while(a)putchar(buf0[a--]);
		putchar('\n');
	}
	//piu(x): Put a non-positive integer x to stdout.
	//Require: |IntToString(x)| < lo.
	template<class I>inline void piu(I x){
		do buf0[++a]=(char(x%10)^'0');while(x/=10);
		while(a)putchar(buf0[a--]);
		putchar('\n');
	}
};
using IO::gi;
using IO::giu;
using IO::gs;
using IO::gch;
using IO::pi;
using IO::piu;

const int p=1000000007;
const int ps2=p-2;
inline void add(int &x){if(x>=p)x-=p;}
inline void sub(int &x){if(x< 0)x+=p;}
#define MUL(a,b) ((0ll|(a))*(b)%p)
template<class T>int expo(int a,T b){
	int s(1);
	while(b){if(b&1)s=MUL(s,a);b>>=1;a=MUL(a,a);}
	return s;
}
int expo(int a){
	int b(ps2),s(1);
	while(b){if(b&1)s=MUL(s,a);b>>=1;a=MUL(a,a);}
	return s;
}

const int MAXN=105,LIM=10005;
int C[MAXN],B[MAXN],Ans[MAXN],F[LIM];
signed main(){
#ifdef ONLINE_JUDGE
	//freopen("problemname.in","r",stdin);
	//freopen("problemname.out","w",stdout);
#endif
	int N;
	giu(N);

	int i;
	rep(i,1,N)giu(C[i]);
	rep(i,2,N)giu(B[i]);

	int Dm,Sm,T,k,c,B1;
	auto solve=[&](){
		Dm=Sm=T=0;
		memset(F,0,sizeof(F));
		F[0]=1;
		B[1]=B1;
		rep(i,1,N){
			c=C[i]+1;
			Sm+=(Dm+=B[i]);
			//ERR("i=%d Sm=%d\n",i,Sm);
			per(k,T-1,0)sub(F[k+c]-=F[k]);
			T+=c-1;
			c=0;
			rep(k,0,T){add(c+=F[k]);F[k]=c;}
			per(k,min(Sm-1,T),0)F[k]=0;
		}
		c=0;
		rep(k,max(0,Sm),T)add(c+=F[k]);
	};
	Dm=Sm=T=0;
	int Lb,Rb=100000;
	rep(i,1,N){
		Sm-=(Dm+=B[i]);
		T+=C[i];
		cmn(Rb,(T+Sm)/i);
	}
	Lb=Sm/N;
	//ERR("Lb=%d Rb=%d\n",Lb,Rb);
	rep(B1,Lb,Rb){
		solve();
		Ans[B1-Lb]=c;
	}
	
	T=1;
	rep(i,1,N)T=T*(C[i]+1ll)%p;

	giu(i);
	while(i--){
		gi(c);
		if(c<Lb)piu(T);else if(c>Rb)puts("0");
		else piu(Ans[c-Lb]);
	}
	return 0;
}
### Prompt

Please create a solution in Cpp to the following 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.

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
#define rep(i,a,b) for(i=(a);i<=(b);++i)
#define per(i,a,b) for(i=(a);i>=(b);--i)
#define REP(i,a,b) for(i=(a);i< (b);++i)
#define PER(i,a,b) for(i=(a);i> (b);--i)
#define ERR(...) fprintf(stderr,__VA_ARGS__)
template<class T>inline void cmn(T &x,const T &a){if(a<x)x=a;}
template<class T>inline void cmx(T &x,const T &a){if(x<a)x=a;}
template<class T>inline bool bmn(T &x,const T &a){if(a<x){x=a;return true;}else return false;}
template<class T>inline bool bmx(T &x,const T &a){if(x<a){x=a;return true;}else return false;}

//Fast IO libs.
//This fast IO lib occupies the stdin once a read operation is performed.
namespace IO{
	//Input buffer size. 
	const int l=1<<20;
	//Output buffer size. 
	const int lo=21;
	char buf[l],*s,*t,c;bool f;
	inline void gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			c=s==t?EOF:*s++;
		}else c=*s++;
	}
	//gi(x): Get an integer from stdin and write it to x.
	template<class I>inline void gi(I &x){
		x=0;f=false;gc();while(c<'0'||c>'9'){if(c=='-')f=true;gc();}
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}if(f)x=-x;
	}
	//giu(x): Get a non-positive integer from stdin and write it to x.
	template<class I>inline void giu(I &x){
		x=0;f=false;gc();while(c<'0'||c>'9')gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}if(f)x=-x;
	}
	//gs(x): Get a string from stdin and write the string length to n.
	inline void gs(char *S,int &n){
		n=0;
		gc();while(!isgraph(c))gc();while(isgraph(c)){S[n++]=c;gc();}
	}
	//gch(x): Get a char from stdin.
	inline void gch(char &s){
		gc();while(!isgraph(c))gc();s=c;
	}
	char buf0[lo];int a;
	//pi(x): Put an integer x to stdout.
	//Require: |IntToString(x)| < lo.
	template<class I>inline void pi(I x){
		if(x<0){putchar('-');x=-x;}
		do buf0[++a]=(char(x%10)^'0');while(x/=10);
		while(a)putchar(buf0[a--]);
		putchar('\n');
	}
	//piu(x): Put a non-positive integer x to stdout.
	//Require: |IntToString(x)| < lo.
	template<class I>inline void piu(I x){
		do buf0[++a]=(char(x%10)^'0');while(x/=10);
		while(a)putchar(buf0[a--]);
		putchar('\n');
	}
};
using IO::gi;
using IO::giu;
using IO::gs;
using IO::gch;
using IO::pi;
using IO::piu;

const int p=1000000007;
const int ps2=p-2;
inline void add(int &x){if(x>=p)x-=p;}
inline void sub(int &x){if(x< 0)x+=p;}
#define MUL(a,b) ((0ll|(a))*(b)%p)
template<class T>int expo(int a,T b){
	int s(1);
	while(b){if(b&1)s=MUL(s,a);b>>=1;a=MUL(a,a);}
	return s;
}
int expo(int a){
	int b(ps2),s(1);
	while(b){if(b&1)s=MUL(s,a);b>>=1;a=MUL(a,a);}
	return s;
}

const int MAXN=105,LIM=10005;
int C[MAXN],B[MAXN],Ans[MAXN],F[LIM];
signed main(){
#ifdef ONLINE_JUDGE
	//freopen("problemname.in","r",stdin);
	//freopen("problemname.out","w",stdout);
#endif
	int N;
	giu(N);

	int i;
	rep(i,1,N)giu(C[i]);
	rep(i,2,N)giu(B[i]);

	int Dm,Sm,T,k,c,B1;
	auto solve=[&](){
		Dm=Sm=T=0;
		memset(F,0,sizeof(F));
		F[0]=1;
		B[1]=B1;
		rep(i,1,N){
			c=C[i]+1;
			Sm+=(Dm+=B[i]);
			//ERR("i=%d Sm=%d\n",i,Sm);
			per(k,T-1,0)sub(F[k+c]-=F[k]);
			T+=c-1;
			c=0;
			rep(k,0,T){add(c+=F[k]);F[k]=c;}
			per(k,min(Sm-1,T),0)F[k]=0;
		}
		c=0;
		rep(k,max(0,Sm),T)add(c+=F[k]);
	};
	Dm=Sm=T=0;
	int Lb,Rb=100000;
	rep(i,1,N){
		Sm-=(Dm+=B[i]);
		T+=C[i];
		cmn(Rb,(T+Sm)/i);
	}
	Lb=Sm/N;
	//ERR("Lb=%d Rb=%d\n",Lb,Rb);
	rep(B1,Lb,Rb){
		solve();
		Ans[B1-Lb]=c;
	}
	
	T=1;
	rep(i,1,N)T=T*(C[i]+1ll)%p;

	giu(i);
	while(i--){
		gi(c);
		if(c<Lb)piu(T);else if(c>Rb)puts("0");
		else piu(Ans[c-Lb]);
	}
	return 0;
}
```