#CF2044F. F. Easy Demon Problem

F. Easy Demon Problem

F. Easy Demon Problem
时间限制:每测试 44
内存限制:每测试 256256 MB

对于任意一个网格,Robot 将其美丽值定义为网格中所有元素之和。

Robot 给你一个长度为 nn 的数组 aa 和一个长度为 mm 的数组 bb。你构造一个 nnmm 列的网格 MM,使得对于所有 1in1 \le i \le n1jm1 \le j \le m,有 Mi,j=aibjM_{i,j} = a_i \cdot b_j

随后,Robot 给你 qq 个询问,每个询问包含一个整数 xx。对于每个询问,判断是否可能恰好执行一次以下操作,使得 MM 的美丽值变为 xx

  • 选择整数 rrcc,满足 1rn1 \le r \le n1cm1 \le c \le m
  • 将所有满足 i=ri=rj=cj=c 或两者均满足的有序对 (i,j)(i, j) 对应的 Mi,jM_{i,j} 设为 00

注意,询问不持久化,即在回答过程中你并不实际将任何元素设为 00 —— 你只需要输出是否存在这样的 rrcc,使得上述操作后网格的美丽值为 xx。另外,你必须对每个询问都执行该操作(即便原网格的美丽值已经等于 xx)。

输入格式
第一行包含三个整数 nn, mm, qq (1n,m21051 \le n, m \le 2 \cdot 10^5, 1q51041 \le q \le 5 \cdot 10^4) —— 分别表示 aa 的长度、bb 的长度以及询问的个数。
第二行包含 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n (0ain0 \le |a_i| \le n)。
第三行包含 mm 个整数 b1,b2,,bmb_1, b_2, \dots, b_m (0bim0 \le |b_i| \le m)。
接下来的 qq 行每行包含一个整数 xx (1x21051 \le |x| \le 2 \cdot 10^5),表示你希望通过将某行和某列的所有元素置 00 后达到的美丽值。

输出格式
对于每个询问,如果存在一种执行上述操作的方式使得美丽值为 xx,则输出 YES(不包含引号),否则输出 NO
YESNO 的大小写不限(例如 yES, yes, Yes 均可)。

样例
输入

3 3 6
-2 3 -3
-2 2 -1
-1
1
-2
2
-3
3

输出

NO
YES
NO
NO
YES
NO

输入

5 5 6
1 -2 3 0 0
0 -2 5 0 -3
4
-3
5
2
-1
2

输出

YES
YES
YES
YES
NO
YES

说明
在第二个例子中,网格为
00 2-2 55 00 3-3
00 44 10-10 00 66
00 6-6 1515 00 9-9
00 00 00 00 00
00 00 00 00 00

通过执行操作 r=4r=4, c=2c=2,得到如下网格:
00 00 55 00 3-3
00 00 10-10 00 66
00 00 1515 00 9-9
00 00 00 00 00
00 00 00 00 00
其美丽值为 44,因此输出 YES

第二个询问中选择 r=3r=3, c=5c=5 可得到美丽值 3-3
第三个询问中选择 r=3r=3, c=3c=3 可得到美丽值 55