Codeforces Round 993 (Div. 4) |
---|
Finished |
For an arbitrary grid, Robot defines its beauty to be the sum of elements in the grid.
Robot gives you an array a of length n and an array b of length m. You construct a n by m grid M such that Mi,j=ai⋅bj for all 1≤i≤n and 1≤j≤m.
Then, Robot gives you q queries, each consisting of a single integer x. For each query, determine whether or not it is possible to perform the following operation exactly once so that M has a beauty of x:
Note that queries are not persistent, meaning that you do not actually set any elements to 0 in the process — you are only required to output if it is possible to find r and c such that if the above operation is performed, the beauty of the grid will be x. Also, note that you must perform the operation for each query, even if the beauty of the original grid is already x.
The first line contains three integers n, m, and q (1≤n,m≤2⋅105,1≤q≤5⋅104) — the length of a, the length of b, and the number of queries respectively.
The second line contains n integers a1,a2,…,an (0≤|ai|≤n).
The third line contains m integers b1,b2,…,bm (0≤|bi|≤m).
The following q lines each contain a single integer x (1≤|x|≤2⋅105), the beauty of the grid you wish to achieve by setting all elements in a row and a column to 0.
For each testcase, output "YES" (without quotes) if there is a way to perform the aforementioned operation such that the beauty is x, and "NO" (without quotes) otherwise.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
3 3 6-2 3 -3-2 2 -1-11-22-33
NO YES NO NO YES NO
5 5 61 -2 3 0 00 -2 5 0 -34-352-12
YES YES YES YES NO YES
In the second example, the grid is
0 -2 5 0 -3
0 4 -10 0 6
0 -6 15 0 -9
0 0 0 0 0
0 0 0 0 0
By performing the operation with r=4 and c=2, we create the following grid:
0 0 5 0 -3
0 0 -10 0 6
0 0 15 0 -9
0 0 0 0 0
0 0 0 0 0
which has beauty 4. Thus, we output YES.
In the second query, selecting r=3 and c=5 creates a grid with beauty −3.
In the third query, selecting r=3 and c=3 creates a grid with beauty 5.
Name |
---|