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:
#include <iostream>
#include <fstream>
#include <cstdio>

#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <stack>

#include <functional>
#include <utility>
#include <algorithm>
#include <cmath>
#include <iterator>
#include <iomanip>
#include <numeric>

#include <cassert>
#include <random>
#include <chrono>

#include <complex>
#include <climits>

using namespace std;

#define ll long long
#define print pair<int,int>
#define prii pair<int,int>
#define m_p make_pair
#define INF (int)1e18

namespace __time {
	clock_t t;
	double get_time() {
		return (double)(clock() - t) / CLOCKS_PER_SEC;
	}
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll mod = 1e9 + 7;
const ll N = 1e2 + 1;
const ll M = 5e3 + 110;
const ll Q = 1e5 + 10;
const ll SUM = 1e4 + 1;

int c[N], b[N], xr[Q];
int sum_b[N][N], hyper_sum_b[N][N], pref_c[N];
ll ans[M];

int get_id(int x) {
	return x + (int)5e3;
}

double get_fir(int l, int r, int sum_a) {
	return  ((double)sum_a - hyper_sum_b[l][r]) / (r - l + 1);
}

template <typename T>
T add(T n) {
	int ans = n % mod;
	if (ans < 0) ans += mod;
	return ans;
}

template <typename T, typename... Args>
T add(T n, Args... rest) {
	int ans = (n + add(rest...)) % mod;
	if (ans < 0) ans += mod;
	return ans;
}

template <typename T>
T mul(T n) {
	return n % mod;
}

template <typename T, typename... Args>
T mul(T n, Args... rest) {
	return ((n % mod) * mul(rest...)) % mod;
}

void $main()
{
	int n; cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> c[i];
	for (int i = 0; i < n - 1; ++i)
		cin >> b[i];

	int q; cin >> q;
	for (int i = 0; i < q; ++i)
		cin >> xr[i];

	for (int i = 0; i < n; ++i) {
		pref_c[i] = (!i ? c[i] : pref_c[i - 1] + c[i]);

		for (int j = i + 1; j < n; ++j) {
			sum_b[i][j] = sum_b[i][j - 1] + b[j - 1];
			hyper_sum_b[i][j] = hyper_sum_b[i][j - 1] + sum_b[i][j];
		}
	}

	int maxima = 100, minima = 0;
	for (int i = 0; i < n; ++i) {
		int min_a1 = floor(get_fir(0, i, 0));
		int max_a1 = floor(get_fir(0, i, pref_c[i]));
		maxima = min(max_a1, maxima); // maxima <=100
		minima = min(min_a1, minima); // minima >-5e3
	}

	for (int x = minima; x <= maxima; ++x) {
		vector<vector<ll>> dp(N, vector<ll>(pref_c[n - 1] + 1));

		for (int i = max(0, x); i <= c[0]; ++i)
			++dp[0][i];
		for (int i = 1; i < n; ++i) {
			//v3.0
			vector<ll> pref_dp(pref_c[i - 1] + 2);
			for (int s = 1; s <= pref_c[i - 1]+1; ++s)
				pref_dp[s] = add(pref_dp[s], pref_dp[s - 1], dp[i - 1][s - 1]);

			int good = x * (i + 1) + hyper_sum_b[0][i];
			for (int s_j = 0; s_j <= pref_c[i]; ++s_j) {
				if (s_j < good) continue;
				int lst_s = s_j;
				int fir_s = s_j - c[i];

				fir_s = max(0, fir_s);
				lst_s = min(pref_c[i - 1], lst_s);
				if (fir_s <= lst_s) {
					dp[i][s_j] = add(pref_dp[lst_s + 1], -pref_dp[fir_s]);
				}
			}
			//

			/*v2.0
			*
			int good = x * (i+1) + hyper_sum_b[0][i];
			for (int s = 0; s <= pref_c[i - 1]; ++s) {
				for (int j = max(0,good); j <= c[i]; ++j)
					dp[i][s + j] = add(dp[i][s + j], dp[i - 1][s]);
				--good;
			}*/

			/*v1.0
			*
			for (int s = 0; s <= pref_c[i - 1]; ++s) {
				for (int j = 0; j <= c[i]; ++j) {
					int a1 = floor(get_fir(0, i, s + j));
					if (a1 < x) continue;

					dp[i][s + j] = add(dp[i][s + j], dp[i - 1][s]);
				}
			}*/
		}

		for (int s = 0; s <= pref_c[n - 1]; ++s)
			ans[get_id(x)] = add(ans[get_id(x)], dp[n - 1][s]);
	}

	for (int i = 0; i < q; ++i) {
		int id = get_id(min(max(minima, xr[i]), maxima + 1));
		cout << ans[id] << '\n';
	}
}

int main()
{
	setlocale(LC_ALL, "Russian");

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#else
	//freopen("kbest.in", "r", stdin);
	//freopen("kbest.out", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	$main();

	return 0;
}