F. Easy Demon Problem
binary search; brute force; data structures; math; number theory
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 \(M_{i,j}=a_i\cdot b_j\) for all \(1 \leq i \leq n\) and \(1 \leq j \leq 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\): Choose integers \(r\) and \(c\) such that \(1 \leq r \leq n\) and \(1 \leq c \leq m\) Set \(M_{i,j}\) to be \(0\) for all ordered pairs \((i,j)\) such that \(i=r\), \(j=c\), or both. 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 \leq n,m \leq 2\cdot 10^5, 1 \leq q \leq 5\cdot 10^4\)) — the length of \(a\), the length of \(b\), and the number of queries respectively.The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \leq |a_i| \leq n\)).The third line contains \(m\) integers \(b_1, b_2, \ldots, b_m\) (\(0 \leq |b_i| \leq m\)).The following \(q\) lines each contain a single integer \(x\) (\(1 \leq |x| \leq 2\cdot 10^5\)), 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).
In the second example, the grid is 0 -2 5 0 -30 4 -10 0 60 -6 15 0 -90 0 0 0 00 0 0 0 0By performing the operation with \(r=4\) and \(c=2\), we create the following grid:0 0 5 0 -30 0 -10 0 60 0 15 0 -90 0 0 0 00 0 0 0 0which 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\).