思路

这个问题的核心在于“连续”、“非空”以及“乘积均相同”这几个条件。

1. 乘积相同的含义 数组中的元素只有 $1$ 和 $2$。任何一个子数组的乘积都是 $2$ 的某个次幂（包括 $2^0=1$）。要想让 $z$ 个子数组的乘积都相同，那么它们的乘积必然都等于同一个值 $P$。这个值 $P$ 也必须是 $2$ 的幂。

2. 与 2 的数量挂钩 一个子数组的乘积由其中 $2$ 的数量决定。如果一个子数组有 $k$ 个 $2$，那么它的乘积就是 $2^k$。因此，“所有子数组乘积相同”等价于“所有子数组包含的 $2$ 的数量相同”。

题目内容

Tk 的朋友给了他一个长度为 $n$ 、仅由 {$1,2$ } 构成的数组 {$a_1,a_2,...,a_n$}。Tk 对这个数组很感兴趣，他将对数组进行 $m$ 次操作。

每次操作给出三个整数 $x,y,z$ ，含义如下：

• 先将 $a_z$ 修改为 $y$ (其中 $y∈${$1,2$});

• 修改之后，Tk 想知道是否可以将整个数组划分为恰好 $z$ 个连续且非空的段，使得这 $z$ 段的乘积均相同。

对于每次操作，请输出结果：若可以，输出 $Yes$ ；否则输出 $NO$ 。

注意：每次修改会影响数组的当前状态，并用于后续操作。

【名词解释】

划分为 $z$ 段：选择 $z-1$ 个切分点，将数组分成 $z$ 个连续且非空的段，覆盖整个数组且两两不交。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1≦T≦10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(1≦n,m≦2×10^5)$ 分别表示数组长度与操作次数；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦ a_i ≦ 2)$ ；

接下来 $m$ 行，每行输入三个整数

$x,y,z(1 ≦x≦n,1≦y≦2,1≦z≦n)$ ，表示一次操作。

除此之外，保证单个测试文件的 $n$ 之和 、$m$ 之和均不超过 $2×10^5$ 。

输出描述

对于每组测试数据，输出 $m$ 行。对每次操作，若可以完成所需划分，输出 $Yes$ ，否则输出 $No$ 。

样例1

输入

2
4 4
1 2 1 2
1 1 1
2 1 2
3 2 2
4 2 3
3 3
1 1 1
2 1 2
1 2 2
3 2 1

输出

Yes
No
Yes
No
Yes
No
Yes

说明

对于第一组数据，初始数组为 {$1,2,1,2$} 。

• 第一次操作后数组变为 {$1,2,1,2$} 可以分割为 {$1,2,1,2$} 满足条件输出 $Yes$ 。

• 第二次操作后数组为 {$1,1,1,2$ } 无法分割为两个乘积相同子段。