Description：

定义二元运算 $opt$ ： $$ x\text{ opt }y= \begin{cases} x+y,&\text{if $x<y$} \\ x-y,&\text{if $x\geqslant y$} \end{cases} $$ 给定 $n$ 个数 $a_i$ 和 $m$ 个数 $b_i$ ， $q$ 次询问有多少对 $(i,j)$ 满足 $\text{$ a i $ opt $ b j $}=k$ 。

$1\leqslant n,m,q,a_i,b_i\leqslant50000$

Solution：

分治 $+FFT$ ，对于当前区间 $[L,R]$ ，把 $A$ 的 $[L,mid]$ 和 $B$ 的 $[mid+1,R]$ 卷积起来，然后累加答案，另一个同理，最后 $O(1)$ 回答询问即可，不要忘了 $0$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m,q;

#define MAXN 200010

int ca[MAXN],cb[MAXN];

long long ans[MAXN];

struct comp

{

	double r,i;

	comp(double r_ = 0.0,double i_ = 0.0){r = r_;i = i_;}

}a[MAXN],b[MAXN];

inline comp operator + (comp a,comp b){return (comp){a.r + b.r,a.i + b.i};}

inline comp operator - (comp a,comp b){return (comp){a.r - b.r,a.i - b.i};}

inline comp operator * (comp a,comp b){return (comp){a.r * b.r - a.i * b.i,a.r * b.i + a.i * b.r};}

int rev[MAXN];

const double PI = acos(-1);

inline void FFT(comp f[],int l,int type)

{

	for(register int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(register int i = 2;i <= l;i = i << 1)

	{

		register comp wn = comp(cos(-type * 2 * PI / i),sin(-type * 2 * PI / i));

		for(register int j = 0;j < l;j += i)

		{

			register comp w = comp(1,0);

			for(register int k = j;k < j + i / 2;++k)

			{

				register comp u = f[k],t = w * f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				w = w * wn;

			}

		}

	}

	if(type == -1)

	{

		for(register int i = 0;i < l;++i)f[i].r = f[i].r / l;

	}

	return;

}

void solve(int L,int R)

{

	if(L == R)

	{

		ans[0] += 1ll * ca[L] * cb[L];

		return;

	}

	register int mid = ((L + R) >> 1);

	solve(L,mid);solve(mid + 1,R);

	register int l = 0,len = 1;

	for(;len <= (R - L + 1);len = len << 1)++l;

	for(register int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	for(register int i = 0;i < len;++i)a[i].r = a[i].i = b[i].r = b[i].i = 0.0;

	for(register int i = L;i <= mid;++i)a[i - L].r = ca[i];

	for(register int i = mid + 1;i <= R;++i)b[i - mid - 1].r = cb[i];

	FFT(a,len,1);FFT(b,len,1);

	for(register int i = 0;i < len;++i)a[i] = a[i] * b[i];

	FFT(a,len,-1);

	for(register int i = 0;i < len;++i)ans[i + L + mid + 1] += (long long)(a[i].r + 0.5);

	for(register int i = 0;i < len;++i)a[i].r = a[i].i = b[i].r = b[i].i = 0.0;

	for(register int i = mid + 1;i <= R;++i)a[i - mid - 1].r = ca[i];

	for(register int i = L;i <= mid;++i)b[mid - i].r = cb[i];

	FFT(a,len,1);FFT(b,len,1);

	for(register int i = 0;i < len;++i)a[i] = a[i] * b[i];

	FFT(a,len,-1);

	for(register int i = 0;i < len;++i)ans[i + 1] += (long long)(a[i].r + 0.5);

	return;

}

void work()

{

	scanf("%d%d%d",&n,&m,&q);

	register int x;

	memset(ca,0,sizeof(ca));

	memset(cb,0,sizeof(cb));

	memset(ans,0,sizeof(ans));

	for(register int i = 1;i <= n;++i)

	{

		x = rd();

		++ca[x];

	}

	for(register int i = 1;i <= m;++i)

	{

		x = rd();

		++cb[x];

	}

	solve(0,50000);

	for(register int i = 1;i <= q;++i)

	{

		x = rd();

		printf("%lld\n",ans[x]);

	}

	return;

}

int main()

{

	register int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}