Problem: Problem

Given a sequence A with n elements, a sequence B with m elements, q queries each consisting of an integer c.
For each query
The absolute value of the difference between the sum of all [la, ra] in sequence A and the sum of all [lb, rb] in sequence B is c. La, ra, lb, rb (0 ≤ la ≤ ra ≤ ra ≤ Find the number of combinations of n−1, 0 ≤ lb ≤ rb ≤ m−1, sequence numbers start from 0).

Constraints

* 1 ≤ n, m ≤ 4 × 104
* 1 ≤ q ≤ 105
* 1 ≤ ai, bi ≤ 5
* 0 ≤ ci ≤ 2 × 105

Input


n m q
a0 a1 ... an−1
b0 b1 ... bm−1
c0
c1
...
cq−1


All inputs are given as integers.
The number of elements n and m in the sequence and the number of queries q are given in the first row.
The elements of sequence A are given in the second row, and the elements of sequence B are given in the third row, separated by blanks.
The value ci of each query is given from the 4th line to the q line.

Output

The output consists of q lines. Print the number of combinations for each query in turn on one line.

Examples

Input

3 3 1
1 2 3
3 1 2
3


Output

6


Input

5 4 2
1 2 3 4 5
2 2 2 2
11
12


Output

3
4

Solution (in CPP):

Solution:
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cctype>
#include <cassert>
#include <limits>
#include <functional>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#if defined(_MSC_VER) || __cplusplus > 199711L
#define aut(r,v) auto r = (v)
#else
#define aut(r,v) __typeof(v) r = (v)
#endif
#define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
using namespace std;
typedef vector<int> vi; typedef pair<int, int> pii; typedef vector<pair<int, int> > vpii; typedef long long ll;
template<typename T, typename U> inline void amin(T &x, U y) { if(y < x) x = y; }
template<typename T, typename U> inline void amax(T &x, U y) { if(x < y) x = y; }

template<int MOD>
struct ModInt {
	static const int Mod = MOD;
	unsigned x;
	ModInt() : x(0) {}
	ModInt(signed sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	ModInt(signed long long sig) { int sigt = sig % MOD; if(sigt < 0) sigt += MOD; x = sigt; }
	int get() const { return (int)x; }

	ModInt &operator+=(ModInt that) { if((x += that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator-=(ModInt that) { if((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
	ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
	ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }

	ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
	ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
	ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
	ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }

	ModInt inverse() const {
		signed a = x, b = MOD, u = 1, v = 0;
		while(b) {
			signed t = a / b;
			a -= t * b; std::swap(a, b);
			u -= t * v; std::swap(u, v);
		}
		if(u < 0) u += Mod;
		ModInt res; res.x = (unsigned)u;
		return res;
	}
};

template<int MOD, int OmegaPrimI, int OmegaMax>
struct NTT {
	typedef ModInt<MOD> fft_mint;
	static fft_mint OmegaPrim;
	static fft_mint Omega[OmegaMax + 1];

	static void fft_init() {
		if(Omega[OmegaMax].get() != 0) return;
		fft_mint x = OmegaPrim;
		for(int i = OmegaMax; i >= 0; i --) {
			Omega[i] = x;
			x *= x;
		}
	}

	//a?????´?£???????
	static void fft_main(int logn, const bool inv, fft_mint a[]) {
		fft_init();
		int n = 1 << logn;
		fft_mint ww = Omega[logn];
		if(inv) ww = ww.inverse();
		for(int m = n, mi = 0; m >= 2; m >>= 1, mi ++) {
			int mh = m >> 1;
			fft_mint w = 1;
			rep(i, mh) {
				for(int j = i; j < n; j += m) {
					int k = j + mh;
					fft_mint x = a[j] - a[k];
					a[j] += a[k];
					a[k] = w * x;
				}
				w *= ww;
			}
			ww *= ww;
		}
		int i = 0;
		reu(j, 1, n - 1) {
			for(int k = n >> 1; k > (i ^= k); k >>= 1);
			if(j < i) swap(a[i], a[j]);
		}
	}

	static void fft(int logn, fft_mint a[]) { fft_main(logn, false, a); }
	static void inverse_fft(int logn, fft_mint a[]) {
		fft_main(logn, true, a);
		int n = 1 << logn;
		fft_mint invn = fft_mint(n).inverse();
		rep(i, n) a[i] *= invn;
	}

	//v, w?????´?£???????v??????????????????
	//v, w??????????????? 2^logn, logn???ceil(log_2(size(v) + size(w)))??????
	static void convolution(fft_mint v[], fft_mint w[], int logn) {
		fft(logn, v); fft(logn, w);
		rep(i, 1 << logn) v[i] *= w[i];
		inverse_fft(logn, v);
	}
};
template<int MOD, int OmegaPrimI, int OmegaMax>
typename NTT<MOD, OmegaPrimI, OmegaMax>::fft_mint NTT<MOD, OmegaPrimI, OmegaMax>::OmegaPrim = OmegaPrimI;
template<int MOD, int OmegaPrimI, int OmegaMax>
typename NTT<MOD, OmegaPrimI, OmegaMax>::fft_mint NTT<MOD, OmegaPrimI, OmegaMax>::Omega[OmegaMax + 1];

typedef NTT<998244353, 31, 23> ntt1;
typedef NTT<1004535809, 848723745, 20> ntt2;
typedef ntt1::fft_mint mint1;
typedef ntt2::fft_mint mint2;

int exgcd(int a, int b, int &g) {
	int u = 1, v = 0;
	while(b) {
		int t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	g = a;
	return u;
}

long long crt(long long a1, long long n1, int a2, int n2, int t, int g, long long &resn) {
	if((a1 - a2) % g != 0) return -1;
	int n2_g = n2 / g;
	int d = (a2 - a1) / g % n2_g;
	int h = (long long)d * t % n2_g;
	if(h < 0) h += n2_g;
	long long n = n1 * n2_g;
	long long a = a1 + n1 * h;
	resn = n;
	return a;
}

void convolution(const int x[], const int y[], int logn, long long res[]) {
	ntt1::fft_init();
	ntt2::fft_init();

	int N = 1 << logn;
	vector<int> v(N), w(N);
	rep(i, N) v[i] = x[i] % mint1::Mod;
	rep(i, N) w[i] = y[i] % mint1::Mod;
	ntt1::convolution((mint1*)&v[0], (mint1*)&w[0], logn);
	rep(i, N) res[i] = v[i];

	rep(i, N) v[i] = x[i] % mint2::Mod;
	rep(i, N) w[i] = y[i] % mint2::Mod;
	ntt2::convolution((mint2*)&v[0], (mint2*)&w[0], logn);
	long long dummy;
	int t, g;
	t = exgcd(mint1::Mod % mint2::Mod, mint2::Mod, g);
	rep(i, N)
		res[i] = crt(res[i], mint1::Mod, v[i], mint2::Mod, t, g, dummy);
}

void solveSub(const vector<int> &a, vector<int> &num) {
	int n = a.size();
	int S = accumulate(all(a), 0);
	int logn = 1;
	while(1 << logn < S * 2 + 1) ++ logn;
	int sum = 0;
	vector<mint1> A(1 << logn), B(1 << logn);
	rep(i, n) {
		++ B[S - sum].x;
		sum += a[i];
		++ A[sum].x;
	}
	ntt1::fft_init();
	ntt1::convolution(&A[0], &B[0], logn);
	num.assign(S * 2 + 1, 0);
	rer(s, 1, S)
		num[s] = A[S + s].x;
}

int main() {
	int n; int m; int q;
	while(~scanf("%d%d%d", &n, &m, &q)) {
		vector<int> a(n);
		for(int i = 0; i < n; ++ i)
			scanf("%d", &a[i]);
		vector<int> b(m);
		for(int i = 0; i < m; ++ i)
			scanf("%d", &b[i]);
		vector<int> numa, numb;
		solveSub(a, numa);
		solveSub(b, numb);
		int logn = 1;
		while(1 << logn < (int)(numa.size() + numb.size()))
			++ logn;
		reverse(all(numb));
		int B = (int)numb.size() - 1;
		numa.resize(1 << logn);
		numb.resize(1 << logn);
		vector<ll> res(numa.size() + numb.size());
		convolution(&numa[0], &numb[0], logn, &res[0]);
		rep(i, q) {
			int c;
			scanf("%d", &c);
			ll ans = 0;
			if(B + c < (int)res.size()) ans += res[B + c];
			if(c != 0 && B - c >= 0) ans += res[B - c];
			printf("%lld\n", ans);
		}
	}
	return 0;
}