#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
#define X first
#define Y second

const ll mod = 1000000007;

ll gcd(ll a, ll b)
{
    a = abs(a);
    b = abs(b);
    if (a==0 or b==0) return a+b;
    return gcd(b,a%b);
}


ll sum(ll a, ll b)
{
    a += b;
    a %= mod;
    return a;
}

ll sub(ll a, ll b)
{
    a += mod-b;
    a %= mod;
    return a;
}

inline ll mul(ll a, ll b)
{
    if (a*b<mod) return a*b;
    return a*b%mod;
}

inline ll pew(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b&1) res = mul(res,a);
        a = mul(a,a);
        b /= 2;
    }
    return res;
}



/*const int MOD = 998244353;
const int root = 31;
const int root_1 = 128805723;
const int root_pw = 1<<23;
const int root = 31;
const int MOD = 469762049;
const int root_1 = 15658735;
const int root_pw = 1<<26;*/


/*void fft (vector<int> & a, bool invert) {
    int n = (int) a.size();

    for (int i=1, j=0; i<n; ++i) {
        int bit = n >> 1;
        for (; j>=bit; bit>>=1)
            j -= bit;
        j += bit;
        if (i < j)
            swap (a[i], a[j]);
    }

    for (int len=2; len<=n; len<<=1) {
        int wlen = invert ? root_1 : root;
        for (int i=len; i<root_pw; i<<=1)
            wlen = int (wlen * 1ll * wlen % mod);
        for (int i=0; i<n; i+=len) {
            int w = 1;
            for (int j=0; j<len/2; ++j) {
                int u = a[i+j],  v = int (a[i+j+len/2] * 1ll * w % mod);
                a[i+j] = u+v < mod ? u+v : u+v-mod;
                a[i+j+len/2] = u-v >= 0 ? u-v : u-v+mod;
                w = int (w * 1ll * wlen % mod);
            }
        }
    }
    if (invert) {
        int nrev = pew(n, mod-2);
        for (int i=0; i<n; ++i)
            a[i] = int (a[i] * 1ll * nrev % mod);
    }
}*/


int parent[600001];
int rnk[600001];

void make_set (int v) {
    parent[v] = v;
    rnk[v] = 0;
}

int find_set (int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets (int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            ++rnk[a];
    }
}

//ll t[1200000];
//ll del[1200000];

/*void build(int n)
{
    for (int i=0;i<=4*n;i++)
    {
        t[i] = 0;
        //del[i] = 0;
    }
}*/

/*void push(int v)
{
    t[2*v].X += del[v];
    t[2*v+1].X += del[v];
    del[2*v] += del[v];
    del[2*v+1] += del[v];
    del[v] = 0;
}*/

/*void update (int v, int tl, int tr, int l, int r, ll val) {
    if (tl==l and tr==r)
    {
        //del[v] += val;

        //t[v] += val*(tr-tl+1);
        return;
    }
    int tm = (tl + tr) / 2;
    //if (del[v]!=0) push(v,tl,tr,tm);
    if (r<=tm)
    {
        update(2*v,tl,tm,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    if (l>tm)
    {
        update(2*v+1,tm+1,tr,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    update(2*v,tl,tm,l,tm,val);
    update(2*v+1,tm+1,tr,tm+1,r,val);
    t[v] = min(t[2*v],t[2*v+1]);
}*/

/*void update (int v, int tl, int tr, int l, int r, ll val) {
    if (tl>=l and tr<=r)
    {
        del[v] += val;
        t[v] += val;
        return;
    }
    int tm = (tl+tr)/2;
    //if (del[v]!=0) push(v);
    if (r<=tm)
    {
        update(2*v,tl,tm,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    if (l>tm)
    {
        update(2*v+1,tm+1,tr,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    update(2*v,tl,tm,l,tm,val);
    update(2*v+1,tm+1,tr,tm+1,r,val);
    t[v] = t[2*v]+t[2*v+1];
}*/


/*pair<ll,ll> get (int v, int tl, int tr, int p) {
    if (tl==tr) return t[v];
    int tm = (tl+tr)/2;
    //push(v);
    if (p<=tm) return t[v]+get(2*v,tl,tm,p);
    else return t[v]+get(2*v+1,tm+1,tr,p);
}*/



int main()
{
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> c(n);
    for (int i=0;i<n;i++) cin >> c[i];
    vector<ll> b(n);
    for (int i=1;i<n;i++) cin >> b[i];
    for (int i=1;i<n;i++) b[i] += b[i-1];
    for (int i=1;i<n;i++) b[i] += b[i-1];
    ll mx = 100;
    ll mx2 = mx*mx;
    ll L = 10000, R = c[0]+1;
    ll P = 0;
    for (ll i=0;i<n;i++)
    {
        P += c[i];
        ll M = b[i]/(i+1);
        if (b[i]%(i+1)>0) M++;
        if (L>-M) L = -M;
        if (P>=b[i])
        {
            M = (P-b[i])/(i+1);
            M++;
            if (R>M) R = M;
        } else
        {
            M = (P-b[i])/(i+1);
            if (P%(i+1)==b[i]%(i+1)) M++;
            if (R>M) R = M;
        }
    }
    vector<ll> ans(R-L+1);
    for (ll z=L;z<=R;z++)
    {
        ll S = z;
        vector<ll> cur(mx2+2), nxt(mx2+2);
        cur[0] = 1;
        for (ll i=0;i<n;i++)
        {
            for (ll j=0;j<=mx2+1;j++) nxt[j] = 0;
            for (ll j=0;j<=mx*i;j++)
            {
                nxt[j] += cur[j];
                if (nxt[j]>=mod) nxt[j] -= mod;
                nxt[j+c[i]+1] += mod-cur[j];
                if (nxt[j+c[i]+1]>=mod) nxt[j+c[i]+1] -= mod;
            }
            for (ll j=1;j<=mx*(i+1)+1;j++)
            {
                nxt[j] += nxt[j-1];
                if (nxt[j]>=mod) nxt[j] -= mod;
            }
            for (ll j=0;j-b[i]<(i+1)*S and j<=mx*(i+1);j++) nxt[j] = 0;
            cur = nxt;
        }
        for (ll j=0;j<=mx2+1;j++) ans[z-L] += cur[j];
        ans[z-L] %= mod;
        if (ans[z-L]<0) ans[z-L] += mod;
    }
    ll q;
    cin >> q;
    for (int i=0;i<q;i++)
    {
        ll x;
        cin >> x;
        if (x>=R)
        {
            cout << ans[R-L] << "\n";
            continue;
        }
        if (x<L)
        {
            cout << ans[0] << "\n";
            continue;
        }
        cout << ans[x-L] << "\n";
    }

}
### Prompt

Please formulate a Cpp solution 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
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
#define X first
#define Y second

const ll mod = 1000000007;

ll gcd(ll a, ll b)
{
    a = abs(a);
    b = abs(b);
    if (a==0 or b==0) return a+b;
    return gcd(b,a%b);
}


ll sum(ll a, ll b)
{
    a += b;
    a %= mod;
    return a;
}

ll sub(ll a, ll b)
{
    a += mod-b;
    a %= mod;
    return a;
}

inline ll mul(ll a, ll b)
{
    if (a*b<mod) return a*b;
    return a*b%mod;
}

inline ll pew(ll a, ll b)
{
    ll res = 1;
    while (b)
    {
        if (b&1) res = mul(res,a);
        a = mul(a,a);
        b /= 2;
    }
    return res;
}



/*const int MOD = 998244353;
const int root = 31;
const int root_1 = 128805723;
const int root_pw = 1<<23;
const int root = 31;
const int MOD = 469762049;
const int root_1 = 15658735;
const int root_pw = 1<<26;*/


/*void fft (vector<int> & a, bool invert) {
    int n = (int) a.size();

    for (int i=1, j=0; i<n; ++i) {
        int bit = n >> 1;
        for (; j>=bit; bit>>=1)
            j -= bit;
        j += bit;
        if (i < j)
            swap (a[i], a[j]);
    }

    for (int len=2; len<=n; len<<=1) {
        int wlen = invert ? root_1 : root;
        for (int i=len; i<root_pw; i<<=1)
            wlen = int (wlen * 1ll * wlen % mod);
        for (int i=0; i<n; i+=len) {
            int w = 1;
            for (int j=0; j<len/2; ++j) {
                int u = a[i+j],  v = int (a[i+j+len/2] * 1ll * w % mod);
                a[i+j] = u+v < mod ? u+v : u+v-mod;
                a[i+j+len/2] = u-v >= 0 ? u-v : u-v+mod;
                w = int (w * 1ll * wlen % mod);
            }
        }
    }
    if (invert) {
        int nrev = pew(n, mod-2);
        for (int i=0; i<n; ++i)
            a[i] = int (a[i] * 1ll * nrev % mod);
    }
}*/


int parent[600001];
int rnk[600001];

void make_set (int v) {
    parent[v] = v;
    rnk[v] = 0;
}

int find_set (int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets (int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (rnk[a] < rnk[b])
            swap(a, b);
        parent[b] = a;
        if (rnk[a] == rnk[b])
            ++rnk[a];
    }
}

//ll t[1200000];
//ll del[1200000];

/*void build(int n)
{
    for (int i=0;i<=4*n;i++)
    {
        t[i] = 0;
        //del[i] = 0;
    }
}*/

/*void push(int v)
{
    t[2*v].X += del[v];
    t[2*v+1].X += del[v];
    del[2*v] += del[v];
    del[2*v+1] += del[v];
    del[v] = 0;
}*/

/*void update (int v, int tl, int tr, int l, int r, ll val) {
    if (tl==l and tr==r)
    {
        //del[v] += val;

        //t[v] += val*(tr-tl+1);
        return;
    }
    int tm = (tl + tr) / 2;
    //if (del[v]!=0) push(v,tl,tr,tm);
    if (r<=tm)
    {
        update(2*v,tl,tm,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    if (l>tm)
    {
        update(2*v+1,tm+1,tr,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    update(2*v,tl,tm,l,tm,val);
    update(2*v+1,tm+1,tr,tm+1,r,val);
    t[v] = min(t[2*v],t[2*v+1]);
}*/

/*void update (int v, int tl, int tr, int l, int r, ll val) {
    if (tl>=l and tr<=r)
    {
        del[v] += val;
        t[v] += val;
        return;
    }
    int tm = (tl+tr)/2;
    //if (del[v]!=0) push(v);
    if (r<=tm)
    {
        update(2*v,tl,tm,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    if (l>tm)
    {
        update(2*v+1,tm+1,tr,l,r,val);
        t[v] = t[2*v]+t[2*v+1];
        return;
    }
    update(2*v,tl,tm,l,tm,val);
    update(2*v+1,tm+1,tr,tm+1,r,val);
    t[v] = t[2*v]+t[2*v+1];
}*/


/*pair<ll,ll> get (int v, int tl, int tr, int p) {
    if (tl==tr) return t[v];
    int tm = (tl+tr)/2;
    //push(v);
    if (p<=tm) return t[v]+get(2*v,tl,tm,p);
    else return t[v]+get(2*v+1,tm+1,tr,p);
}*/



int main()
{
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> c(n);
    for (int i=0;i<n;i++) cin >> c[i];
    vector<ll> b(n);
    for (int i=1;i<n;i++) cin >> b[i];
    for (int i=1;i<n;i++) b[i] += b[i-1];
    for (int i=1;i<n;i++) b[i] += b[i-1];
    ll mx = 100;
    ll mx2 = mx*mx;
    ll L = 10000, R = c[0]+1;
    ll P = 0;
    for (ll i=0;i<n;i++)
    {
        P += c[i];
        ll M = b[i]/(i+1);
        if (b[i]%(i+1)>0) M++;
        if (L>-M) L = -M;
        if (P>=b[i])
        {
            M = (P-b[i])/(i+1);
            M++;
            if (R>M) R = M;
        } else
        {
            M = (P-b[i])/(i+1);
            if (P%(i+1)==b[i]%(i+1)) M++;
            if (R>M) R = M;
        }
    }
    vector<ll> ans(R-L+1);
    for (ll z=L;z<=R;z++)
    {
        ll S = z;
        vector<ll> cur(mx2+2), nxt(mx2+2);
        cur[0] = 1;
        for (ll i=0;i<n;i++)
        {
            for (ll j=0;j<=mx2+1;j++) nxt[j] = 0;
            for (ll j=0;j<=mx*i;j++)
            {
                nxt[j] += cur[j];
                if (nxt[j]>=mod) nxt[j] -= mod;
                nxt[j+c[i]+1] += mod-cur[j];
                if (nxt[j+c[i]+1]>=mod) nxt[j+c[i]+1] -= mod;
            }
            for (ll j=1;j<=mx*(i+1)+1;j++)
            {
                nxt[j] += nxt[j-1];
                if (nxt[j]>=mod) nxt[j] -= mod;
            }
            for (ll j=0;j-b[i]<(i+1)*S and j<=mx*(i+1);j++) nxt[j] = 0;
            cur = nxt;
        }
        for (ll j=0;j<=mx2+1;j++) ans[z-L] += cur[j];
        ans[z-L] %= mod;
        if (ans[z-L]<0) ans[z-L] += mod;
    }
    ll q;
    cin >> q;
    for (int i=0;i<q;i++)
    {
        ll x;
        cin >> x;
        if (x>=R)
        {
            cout << ans[R-L] << "\n";
            continue;
        }
        if (x<L)
        {
            cout << ans[0] << "\n";
            continue;
        }
        cout << ans[x-L] << "\n";
    }

}
```