给定一个 $$$1$$$ 索引数组 $$$a$$$,长度为 $$$n$$$,其中每个元素为 $$$1$$$ 或 $$$2$$$。
处理以下两种类型的 $$$q$$$ 查询:
- "1 s": 检查$$$a$$$中是否存在子数组$$$^{\dagger}$$$,其总和等于$$$s$$$。
- “2 i v”:将 $$$a_i$$$ 更改为 $$$v$$$。
$$$^{\dagger}$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的子数组,如果 $$$b$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$a$$$ 获得。特别是,数组是其自身的子数组。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1\le n,q\le 10^5$$$) - 数组 $$$a$$$ 的长度和查询的数量。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$($$$a_i$$$ 是 $$$1$$$ 或 $$$2$$$)——数组 $$$a$$$ 的元素。
每个测试用例的以下 $$$q$$$ 行中的每一行都包含一些整数。第一个整数 $$$\mathrm{op}$$$ 是 $$$1$$$ 或 $$$2$$$。
- 如果 $$$\mathrm{op}$$$ 为 $$$1$$$,则其后跟随一个整数 $$$s$$$ ($$$1 \leq s \leq 2n$$$)。
- 如果 $$$\mathrm{op}$$$ 是 $$$2$$$,则后面跟着两个整数 $$$i$$$ 和 $$$v$$$($$$1 \leq i \leq n$$$,$$$v$$$ 是 $$$1$$$ 或 $$$2$$$)。
保证所有测试用例的$$$n$$$总和和$$$q$$$总和不超过$$$10^5$$$。
输出
对于$$$\mathrm{op}=1$$$的每个查询,如果存在$$$a$$$的子数组且其总和等于$$$s$$$,则在一行中输出“YES”,否则输出“NO”。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。
示例
输入 #1
2 5 5 2 1 2 1 2 1 5 1 6 1 7 2 4 2 1 7 3 2 2 2 2 1 6 1 5
输出 #1
YES YES NO YES YES NO
注意
考虑第一个例子:
- 第一个查询的答案是“YES”,因为 $$$a_1+a_2+a_3=2+1+2=5$$$。
- 第二个查询的答案是“YES”,因为 $$$a_1+a_2+a_3+a_4=2+1+2+1=6$$$。
- 第三个查询的答案是“NO”,因为我们找不到 $$$a$$$ 中任何总和为 $$$7$$$ 的子数组。
- 第四次查询后,数组 $$$a$$$ 变为 $$$[2,1,2,2,2]$$$。
- 第五个查询的答案是“是”,因为 $$$a_2+a_3+a_4+a_5=1+2+2+2=7$$$。