Mike 收到了一个长度为 $$$n$$$ 的数组 $$$a$$$ 作为生日礼物,并决定测试一下它有多漂亮。
如果有一种方法可以使用一定数量(可能为零)的切片操作来获取元素总和为 $$$s_i$$$ 的数组,则数组将通过第 $$$i$$$ 漂亮测试。
数组切片操作按以下方式进行:
- 假设 $$$mid = \lfloor\frac{max(array) + min(array)}{2}\rfloor$$$,其中 $$$max$$$ 和 $$$min$$$ - 是查找最大和最小数组元素的函数。换句话说,$$$mid$$$ 是 $$$array$$$ 的最大和最小元素之和除以 $$$2$$$ 向下舍入。
- 然后数组被分成两部分 $$$\mathit{left}$$$ 和 $$$right$$$。 $$$\mathit{left}$$$ 数组包含小于或等于 $$$mid$$$ 的所有元素,$$$right$$$ 数组包含大于 $$$mid$$$ 的所有元素。 $$$\mathit{left}$$$ 和 $$$right$$$ 中的元素保持其与 $$$array$$$ 的相对顺序。
- 在第三步中,我们选择要保留 $$$\mathit{left}$$$ 和 $$$right$$$ 数组中的哪一个。所选阵列将替换当前阵列,而另一个阵列将被永久丢弃。
你需要帮助迈克找出$$$q$$$漂亮测试的结果。
请注意,您测试了数组 $$$a$$$ 的漂亮性,因此您以原始(初始)数组 $$$a$$$ 开始每个漂亮性测试。因此,第一个切片(如果需要)始终在数组 $$$a$$$ 上执行。
输入
每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ ——数组 $$$a$$$ 的长度和漂亮测试的总数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, ..., a_n$$$ $$$(1 \le a_i \le 10^6)$$$ — 数组 $$$a$$$ 的内容。
每个测试用例的接下来 $$$q$$$ 行包含一个整数 $$$s_i$$$ $$$(1 \le s_i \le 10^9)$$$ - Mike 希望在第 $$$i$$$ 测试中获得的元素总和。
保证$$$n$$$和$$$q$$$的总和不超过$$$10^5$$$ ($$$\sum n, \sum q \le 10^5$$$)。
输出
打印 $$$q$$$ 行,如果通过相应的漂亮测试,则每行包含“是”,反之则包含“否”。
示例
输入 #1
2 5 5 1 2 3 4 5 1 8 9 12 6 5 5 3 1 3 1 3 1 2 3 9 11
输出 #1
Yes No Yes No Yes No Yes No Yes Yes
注意
第一个测试用例的说明:
1. 我们可以通过以下方式得到总和 $$$s_1 = 1$$$ 的数组: 1.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$。我们选择保留 $$$\mathit{left}$$$ 数组。 1.2 $$$a = [1, 2, 3]$$$,$$$mid = \frac{1+3}{2} = 2$$$,$$$\mathit{left} = [1, 2]$$$,$$$right = [3]$$$。我们选择保留 $$$\mathit{left}$$$ 数组。 1.3 $$$a = [1, 2]$$$, $$$mid = \frac{1+2}{2} = 1$$$, $$$\mathit{left} = [1]$$$, $$$right = [2]$$$。我们选择保留 $$$\mathit{left}$$$ 数组,其总和等于 $$$1$$$。
2. 可以证明,总和 $$$s_2 = 8$$$ 的数组是不可能生成的。
3. 可以通过以下方式生成总和 $$$s_3 = 9$$$ 的数组: 3.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$。我们选择保留 $$$right$$$ 数组,其总和等于 $$$9$$$。
4. 可以证明,总和 $$$s_4 = 12$$$ 的数组是不可能生成的。
5. 我们可以通过以下方式得到总和 $$$s_5 = 6$$$ 的数组: 5.1 $$$a = [1, 2, 3, 4, 5]$$$, $$$mid = \frac{1+5}{2} = 3$$$, $$$\mathit{left} = [1, 2, 3]$$$, $$$right = [4, 5]$$$。我们选择保留$$$\mathit{left}$$$,总和等于$$$6$$$。
第二个测试用例说明:
1. 可以证明,$$$s_1 = 1$$$ 的数组是不可能生成的。
2. 我们可以通过以下方式得到总和 $$$s_2 = 2$$$ 的数组: 2.1 $$$a = [3, 1, 3, 1, 3]$$$, $$$mid = \frac{1+3}{2} = 2$$$, $$$\mathit{left} = [1, 1]$$$, $$$right = [3, 3, 3]$$$。我们选择保留 $$$\mathit{left}$$$ 数组,其总和等于 $$$2$$$。
3. 可以证明,总和 $$$s_3 = 3$$$ 的数组是不可能生成的。
4. 我们可以通过以下方式得到总和 $$$s_4 = 9$$$ 的数组: 4.1 $$$a = [3, 1, 3, 1, 3]$$$, $$$mid = \frac{1+3}{2} = 2$$$, $$$\mathit{left} = [1, 1]$$$, $$$right = [3, 3, 3]$$$。我们选择保留 $$$right$$$ 数组,其总和等于 $$$9$$$。
5. 我们可以通过零切片操作得到总和 $$$s_5 = 11$$$ 的数组,因为数组总和等于 $$$11$$$。