bzoj#P4836. [Lydsy2017年4月月赛]二元运算

[Lydsy2017年4月月赛]二元运算

题目描述

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

现在给定一个长为 nn 的数列 aa 和一个长为 mm 的数列 bb ,接下来有 qq 次询问。

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

输入格式

第一行是一个整数 TT ,表示测试数据的组数。

对于每组测试数据:

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

第二行是 nn 个整数,表示 a1,a2,,ana_1,a_2,\cdots,a_n

第三行是 mm 个整数,表示 b1,b2,,bmb_1,b_2,\cdots,b_m

第四行是 qq 个整数,第 ii 个整数 cic_i 表示第 ii 次查询的数。

输出格式

对于每次查询,输出一行,包含一个整数,表示满足条件的 (i,j)(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%100\% 的数据,1T101\le T\le 100ai,bi,n,m,q5×1040\le a_i,b_i,n,m,q \le 5\times 10^40ci1050\le c_i\le 10^5

题目来源

鸣谢Tangjz提供试题