H. 雪碧喝可乐
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

本题与"可乐喝雪碧"是不同的，你可能需要分别阅读两个版本。两题区别在于 $$$q$$$ 和 $$$x$$$ 的限制条件不同，在这个版本中，$$$1 \le q \le 10^6$$$，且 $$$1\le x \le 10^6$$$。

从前有一只雪碧，他每天都一定会去商店买一瓶可乐。每天商店出售的可乐的口味可能以下是三种之一：

  1. 经典口味，雪碧的最爱，雪碧喝完后有 $$$+1$$$ 的快乐值。

  2. 无糖口味，感觉很一般，雪碧喝完后有 $$$0$$$ 的快乐值。

  3. 樱桃口味，雪碧的噩梦，雪碧喝完后有 $$$-1$$$ 的快乐值。

每天雪碧买完可乐后不一定当天喝完，他可以囤积若干瓶可乐，然后在将来的某一天，把囤积的所有可乐一口气喝完。雪碧一次喝完若干可乐后获得的快乐值为一次喝的所有可乐的快乐值之积。雪碧能得到的快乐值的总和是若干次喝可乐的快乐值之和。

现在雪碧通过魔法获知了未来 $$$n$$$ 天商店的可乐出售情况数组 $$$a$$$，其中 $$$a_i$$$ 代表未来第 $$$i$$$ 天商店出售的可乐的快乐值。他突发奇想，想知道他能否通过囤积和一口气喝完的手段，在把未来 $$$n$$$ 天的所有可乐都喝完后，获得恰好 $$$x$$$ 的快乐值的总和。

乐于思考的雪碧连续想了 $$$q$$$ 个这样的问题，并期待你给他回答。

形式化地，给定长度为 $$$n$$$ 的由 $$$-1, 0, 1$$$ 组成的数组 $$$a$$$，询问是否存在一种方案通过在所有相邻的两数之间填入共 $$$n-1$$$ 个加号和乘号所形成的数学表达式的求值为 $$$x$$$。

Input

第一行一个整数 $$$T$$$ ($$$1\le T\le 10^4$$$)，代表测试用例数。

对于每组测试用例：

  • 第一行两个整数 $$$n,q$$$ ($$$1\le n,q\le 10^6$$$) 分别表示未来天数和询问次数。
  • 第二行 $$$n$$$ 个整数，其中第 $$$i$$$ 个整数 $$$a_i$$$ ($$$a_i\in \{-1,0,1\}$$$) 表示未来第 $$$i$$$ 天商店出售的可乐的快乐值。
  • 接下来 $$$q$$$ 行，每行一个整数 $$$x$$$ ($$$1\le x\le 10^6$$$)，表示雪碧的一个询问。

保证所有测试用例的 $$$n$$$ 之和与 $$$q$$$ 之和均不大于 $$$10^6$$$。

Output

对于每一个询问，如果满足条件则输出一行 Yes，否则输出一行 No。

你可以以任意大小写输出 Yes 和 No（例如，字符串 yEs、yes、Yes 和 YES 将被识别为肯定的回答）。

Example
Input
2
3 2
1 1 0
2
3
3 1
1 0 -1
1
Output
YES
NO
YES
Note

对于第一个测试用例：

  • 显然可以通过方案 $$$1 + 1 + 0 = 2$$$ 得到快乐值 $$$2$$$。

  • 容易证明不存在任何方案得到快乐值 $$$3$$$。

对于第二个测试用例：

  • 可以通过方案 $$$1 + 0 \times -1 = 1$$$ 得到快乐值 $$$1$$$。