题目描述

定义二元运算 $\operatorname{opt}$ 满足

现在给定一个长为 $n$ 的数列 $a$ 和一个长为 $m$ 的数列 $b$ ，接下来有 $q$ 次询问。

每次询问给定一个数字 $c$，你需要求出有多少对 $(i, j)$ 使得 $a_i \operatorname{opt} b_j=c$。

输入格式

第一行是一个整数 $T$ ，表示测试数据的组数。

对于每组测试数据：

第一行是三个整数 $n,m,q$ 。

第二行是 $n$ 个整数，表示 $a_1,a_2,\cdots,a_n$ 。

第三行是 $m$ 个整数，表示 $b_1,b_2,\cdots,b_m$ 。

第四行是 $q$ 个整数，第 $i$ 个整数 $c_i$ 表示第 $i$ 次查询的数。

输出格式

对于每次查询，输出一行，包含一个整数，表示满足条件的 $(i, j)$ 对的个数。

样例输入

2
2 1 5
1 3
2
1 2 3 4 5
2 2 5
1 3
2 4
1 2 3 4 5

样例输出

1
0
1
0
0
1
0
1
0
1

数据范围与约定

对于 $100\%$ 的数据，$1\le T\le 10$，$0\le a_i,b_i,n,m,q \le 5\times 10^4$，$0\le c_i\le 10^5$。

题目来源

鸣谢Tangjz提供试题