G. 字节序列
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

小 i 非常喜欢 utf8 string，因此他为你准备了一个与字节序列有关的挑战。

一个长度为 $$$k$$$ 的由字节$$$^{\text{∗}}$$$组成的序列 $$$[c_1, c_2, \ldots, c_k]$$$ 构成 UTF-8 编码字符，当且仅当它满足以下形式之一：

  • $$$k = 1$$$ 且 $$$0 \leq c_1 \leq 127$$$：即在二进制表示下，形如 $$$[\mathtt{0xxxxxxx}]$$$。
  • $$$k = 2$$$ 且 $$$192 \leq c_1 \leq 223$$$ 且 $$$128 \leq c_2 \leq 191$$$：即在二进制表示下，形如 $$$[\mathtt{110xxxxx}, \mathtt{10xxxxxx}]$$$。
  • $$$k = 3$$$ 且 $$$224 \leq c_1 \leq 239$$$ 且 $$$128 \leq c_2,c_3 \leq 191$$$：即在二进制表示下，形如 $$$[\mathtt{1110xxxx}, \mathtt{10xxxxxx}, \mathtt{10xxxxxx}]$$$。
  • $$$k = 4$$$ 且 $$$240 \leq c_1 \leq 247$$$ 且 $$$128 \leq c_2,c_3,c_4 \leq 191$$$：即在二进制表示下，形如 $$$[\mathtt{11110xxx}, \mathtt{10xxxxxx}, \mathtt{10xxxxxx}, \mathtt{10xxxxxx}]$$$。

一个由字节组成的序列构成 utf8 string，当且仅当它可以被恰好完整地分成若干个 UTF-8 编码字符的拼接。

给定一个长度为 $$$n$$$ 的初始字节序列 $$$a_1, a_2, \ldots, a_n$$$。接下来，小 $$$i$$$ 将会对这个序列进行 $$$q$$$ 次操作，每次操作为以下两种类型之一：

  • $$$1 \ p \ x$$$（$$$1 \leq p \leq n$$$ 且 $$$0 \leq x \leq 255$$$）：将 $$$a_p$$$ 修改为 $$$x$$$。
  • $$$2 \ l \ r$$$（$$$1 \leq l \leq r \leq n$$$）：询问 $$$l$$$ 到 $$$r$$$ 的子区间，即 $$$[a_l, a_{l+1}, \ldots, a_r]$$$，是否构成 utf8 string。

$$$^{\text{∗}}$$$字节指的是介于 $$$0$$$ 到 $$$255$$$ 之间（包括两端）的整数。

Input

第一行包含两个整数 $$$n$$$ 和 $$$q$$$（$$$1 \leq n,q \leq 5 \times 10^5$$$）。

第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \ldots, a_n$$$（$$$0 \leq a_i \leq 255$$$），表示初始序列。

接下来的 $$$q$$$ 行，每行表示一次操作：

  • 对于类型为 $$$1$$$ 的操作，保证 $$$1 \leq p \leq n$$$ 且 $$$0 \leq x \leq 255$$$；
  • 对于类型为 $$$2$$$ 的操作，保证 $$$1 \leq l \leq r \leq n$$$；
Output

对于每个类型为 2 的询问，输出一行：

  • 若对应子区间构成 utf8 string，输出 $$$\mathtt{YES}$$$；
  • 否则，输出 $$$\mathtt{NO}$$$。
Examples
Input
7 7
65 194 128 240 128 128 128
2 1 7
2 2 3
2 2 6
1 4 248
2 1 7
1 4 240
2 5 7
Output
YES
YES
NO
NO
NO
Input
4 4
192 168 1 1
2 1 4
1 1 191
2 1 2
2 3 4
Output
YES
NO
YES
Input
1 1
255
2 1 1
Output
NO