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<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;




typedef complex<double> COMPLEX;
#define MAX 200000
#define SIZE 30

int table_A[40005],table_B[40005];


struct Info{
	Info(int arg_left,int arg_right){
		left = arg_left;
		right = arg_right;
	}
	int left,right;
};

int POW[SIZE];
int LR_rev[2000005];
vector<Info> info;
vector<COMPLEX> V[SIZE];


void calc_swap_pair(int N,int num_pow){

	LR_rev[0] = 0;

	for(int i = 1; i < N; i++){

		if(i%2 == 1){

			LR_rev[i] = LR_rev[i-1]+POW[num_pow-1]; //1を足す代わりにPOW[num_pow-1]を足す

		}else{

			LR_rev[i] = LR_rev[i/2]/2; //半分のインデックスの値に、2を掛ける代わりに2で割る
		}

		if(i < LR_rev[i]){
			info.push_back(Info(i,LR_rev[i]));
		}
	}
}

void calc_COMPLEX(int N){

	for(int LEN = 2,num_pow = 0; LEN <= N; LEN *= 2,num_pow++){

		V[num_pow].resize(LEN/2);

		V[num_pow][0] = COMPLEX(cos(0),sin(0));

		COMPLEX mult = COMPLEX(cos((2*M_PI)/LEN),sin((2*M_PI)/LEN));

		for(int i = 1; i < LEN/2; i++){

			if(i%2 == 1){
				V[num_pow][i] = V[num_pow][i-1]*mult;
			}else{
				V[num_pow][i] = V[num_pow-1][i/2];
			}
		}
	}
}

//離散フーリエ変換
vector<COMPLEX> DFT(vector<COMPLEX> A) {

	int N = A.size();

	/*偶数項を左に、奇数項を右に仕分けるルールで要素数1まで仕分けした場合の、
	 * 最終結果を先に作っておく(ビットが左右反転したものがその位置に来る)*/
	for(int i = 0; i < info.size(); i++){

		swap(A[info[i].left],A[info[i].right]);
	}

	COMPLEX a,add;

	for(int LEN = 2,num_pow = 0; LEN <= N; LEN *= 2,num_pow++){

		for(int start = 0; start < N; start += LEN){
			for(int i = 0; i < LEN/2; i++){
				//マージソートの容量で、配列を更新していく
				a = A[start+i];
				add = V[num_pow][i]*A[start+LEN/2+i];

				A[start+i] = a+add;
				A[start+LEN/2+i] = a-add;
			}
		}
	}
	return A;
}




//離散逆フーリエ変換
vector<COMPLEX> inverseDFT(vector<COMPLEX> A){

	int N = A.size();

	vector<COMPLEX> TMP = DFT(A);

	//係数を入れ替える&サイズNで各要素を割る
	vector<COMPLEX> RET(N);

	for(int i = 0; i < N; i++){

		RET[i] = TMP[(N-i)%N];
		RET[i] = RET[i]/COMPLEX(N,0);
	}

	return RET;
}

vector<COMPLEX> convolution(vector<COMPLEX> A,vector<COMPLEX> B){

	int degree = (A.size()-1)+(B.size()-1)+1;

	int N = 1,num_pow = 0;
	while(N < degree){
		N *= 2;
		num_pow++;
	}

	info.clear();
	calc_swap_pair(N,num_pow);
	calc_COMPLEX(N);

	A.resize(N);
	B.resize(N);

	A = DFT(A);
	B = DFT(B);

	vector<COMPLEX> RET(N);

	for(int i = 0; i < N; i++){

		RET[i] = A[i]*B[i];
	}

	return inverseDFT(RET);
}

int main(){

	POW[0] = 1;
	for(int i = 1; i < SIZE; i++){

		POW[i] = POW[i-1]*2;
	}

	int N,M,num_query;

	scanf("%d %d %d",&N,&M,&num_query);

	table_A[0] = 0;
	for(int i = 1; i <= N; i++){

		scanf("%d",&table_A[i]);
		table_A[i] += table_A[i-1];
	}

	table_B[0] = 0;
	for(int i = 1; i <= M; i++){

		scanf("%d",&table_B[i]);
		table_B[i] += table_B[i-1];
	}


	vector<COMPLEX> P(MAX+1),Q(MAX+1),R(MAX+1);

	for(int i = 0; i <= N; i++){

		P[table_A[i]] += 1;
		Q[table_A[i]] += 1;
	}
	reverse(Q.begin(),Q.end());

	vector<COMPLEX> ret = convolution(P,Q);

	for(int i = 0; i <= MAX-1; i++){

		R[i] = ret[(MAX-1)-i];
	}

	vector<COMPLEX> P2(MAX+1),Q2(MAX+1),R2(MAX+1);

	for(int i = 0; i <= M; i++){

		P2[table_B[i]] += 1;
		Q2[table_B[i]] += 1;
	}
	reverse(Q2.begin(),Q2.end());

	vector<COMPLEX> ret2 = convolution(P2,Q2);

	for(int i = 0; i <= MAX-1; i++){

		R2[i] = ret2[(MAX-1)-i];
	}

	reverse(R2.begin(),R2.end());

	vector<COMPLEX> ret3 = convolution(R,R2);

	int tmp;

	for(int loop = 0; loop < num_query; loop++){

		scanf("%d",&tmp);
		if(tmp == 0){

			printf("%lld\n",(ll)round(ret3[MAX].real()));
		}else{

			printf("%lld\n",(ll)round(ret3[MAX-tmp].real())+(ll)round(ret3[MAX+tmp].real()));
		}
	}

	return 0;
}