310835: CF1896D. Ones and Twos

D. Ones and Twostime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given a $1$-indexed array $a$ of length $n$ where each element is $1$ or $2$.

Process $q$ queries of the following two types:

• "1 s": check if there exists a subarray$^{\dagger}$ of $a$ whose sum equals to $s$.
• "2 i v": change $a_i$ to $v$.

$^{\dagger}$ An array $b$ is a subarray of an array $a$ if $b$ can be obtained from $a$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.

Input

Each test contains multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($1\le n,q\le 10^5$) — the length of array $a$ and the number of queries.

The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($a_i$ is $1$ or $2$) — the elements of array $a$.

Each of the following $q$ lines of each test case contains some integers. The first integer $\mathrm{op}$ is either $1$ or $2$.

• If $\mathrm{op}$ is $1$, it is followed by one integer $s$ ($1 \leq s \leq 2n$).
• If $\mathrm{op}$ is $2$, it is followed by two integers $i$ and $v$ ($1 \leq i \leq n$, $v$ is $1$ or $2$).

It is guaranteed that the sum of $n$ and the sum of $q$ over all test cases both do not exceed $10^5$.

Output

For each query with $\mathrm{op}=1$, output "YES" in one line if there exists a subarray of $a$ whose sum is equals to $s$, otherwise output "NO".

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

ExampleInput

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

Output

YES
YES
NO
YES
YES
NO

Note

Consider the first example:

• The answer for the first query is "YES" because $a_1+a_2+a_3=2+1+2=5$.
• The answer for the second query is "YES" because $a_1+a_2+a_3+a_4=2+1+2+1=6$.
• The answer for the third query is "NO" because we cannot find any subarray of $a$ whose sum is $7$.
• After the fourth query, the array $a$ becomes $[2,1,2,2,2]$.
• The answer for the fifth query is "YES" because $a_2+a_3+a_4+a_5=1+2+2+2=7$.

题目大意：给定一个长度为n的数组a，每个元素为1或2。处理q个查询，有两种类型：

1. "1 s"：检查是否存在一个子数组的和等于s。
2. "2 i v"：将a[i]的值更改为v。

输入数据格式：第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。每个测试用例包含以下内容：

- 第一行包含两个整数n和q（1≤n,q≤10^5），分别表示数组a的长度和查询的数量。
- 第二行包含n个整数a_1,a_2,…,a_n（a_i为1或2），表示数组a的元素。
- 接下来的q行，每行包含一些整数。第一个整数op为1或2。
- 如果op为1，则后面跟一个整数s（1≤s≤2n）。
- 如果op为2，则后面跟两个整数i和v（1≤i≤n，v为1或2）。

保证所有测试用例的n和q之和都不超过10^5。

输出数据格式：对于每个op=1的查询，如果存在一个子数组的和等于s，则输出"YES"，否则输出"NO"。输出可以是任何大小写形式。题目大意：给定一个长度为n的数组a，每个元素为1或2。处理q个查询，有两种类型： 1. "1 s"：检查是否存在一个子数组的和等于s。 2. "2 i v"：将a[i]的值更改为v。 输入数据格式：第一行包含一个整数t（1≤t≤10^4），表示测试用例的数量。每个测试用例包含以下内容： - 第一行包含两个整数n和q（1≤n,q≤10^5），分别表示数组a的长度和查询的数量。 - 第二行包含n个整数a_1,a_2,…,a_n（a_i为1或2），表示数组a的元素。 - 接下来的q行，每行包含一些整数。第一个整数op为1或2。 - 如果op为1，则后面跟一个整数s（1≤s≤2n）。 - 如果op为2，则后面跟两个整数i和v（1≤i≤n，v为1或2）。 保证所有测试用例的n和q之和都不超过10^5。 输出数据格式：对于每个op=1的查询，如果存在一个子数组的和等于s，则输出"YES"，否则输出"NO"。输出可以是任何大小写形式。