Codeforces Round 993 (Div. 4)

菜~~

• F Easy Demon Problem

• References:

  • Codeforces Round 993 (Div. 4) Editorial
  • Codeforces Round 993 (Div. 4)

F. Easy Demon Problem

Description

For an arbitrary grid, Robot defines its beauty to be the sum of elements in the grid.

Robot gives you an array of length and an array of length . You construct a by grid such that for all and .

Then, Robot gives you queries, each consisting of a single integer . For each query, determine whether or not it is possible to perform the following operation exactly once so that has a beauty of :

1. Choose integers and c such that and
2. Set to be for all ordered pairs such that , , or both.

Note that queries are not persistent, meaning that you do not actually set any elements to in the process — you are only required to output if it is possible to find and such that if the above operation is performed, the beauty of the grid will be . Also, note that you must perform the operation for each query, even if the beauty of the original grid is already .

Input

The first line contains three integers $n, , and — the length of , the length of , and the number of queries respectively.

The second line contains integers .

The third line contains integers .

The following lines each contain a single integer , the beauty of the grid you wish to achieve by setting all elements in a row and a column to .

Output

For each testcase, output "YES" (without quotes) if there is a way to perform the aforementioned operation such that the beauty is , 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).

Examples

input

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

output

NO
YES
NO
NO
YES
NO

input

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

output

YES
YES
YES
YES
NO
YES

Note

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 and , 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 . Thus, we output YES.

In the second query, selecting and creates a grid with beauty .

In the third query, selecting and creates a grid with beauty .

Solution

• 参考 F - Easy Demon Problem - tourist

做的时候，把式子拆开了，没简化出乘积形式(thoughtforces)

根据题意有

而题述的operation对的影响是

因此，要使

仅需要找 能否通过 与 的乘积表示
而在实现中，如果通过遍历每一个 以查找对应的 ，那么时间复杂度仍较大，因此尝试将 拆成两个因子 ，即 ，而要想知道是否存在对应的 以及，我们可以反过来考虑

因此我们只需要查找是否存在对应的 以及 ，而使用一个 map 即可实现 的对 以及 的查找，而 和 ，都可以一并在输入时预处理。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
  int n, m, q, x, asum = 0, bsum = 0;
  map<int, bool> mpa, mpb;
  bool flag;
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    cin >> x;
    asum += x;
    mpa[x] = true;
  }
  for (int i = 1; i <= m; i++) {
    cin >> x;
    bsum += x;
    mpb[x] = true;
  }
  auto check = [&](int a, int b) {
    return mpa.count(asum - a) && mpb.count(bsum - b);
  };
  while (q--) {
    cin >> x;
    flag = false;
    for (int i = 1; i * i <= abs(x); ++i)
      if (x % i == 0) {
        if ((flag = (check(i, x / i) || check(x / i, i) || check(-i, -x / i) ||
                     check(-x / i, -i))))
          break;
      }
    if (flag)
      cout << "YES" << endl;
    else
      cout << "NO" << endl;
  }
}
signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int t = 1;
  // cin >> t;
  while (t--) solve();
  return 0;
}