题目描述

小爱丽丝也生活在奥尔菲斯庄园中，有一天，她给一个由 $n$ 块瓷砖组成的环涂色。瓷砖按顺时针从 $0$ 到 $n-1$ 编号。庄园中的颜料只有两种颜色——红色和蓝色，分别用 $0$ 和 $1$ 表示。

爱丽丝喜欢不同颜色交替出现。环中连续若干块瓷砖的颜色如果是交替颜色（也就是说这组瓷砖中除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它左边和右边的颜色都不同），那么它被称为一个交替组。

初始时，编号为 $i$ 的瓷砖颜色是 $c_i$。你需要处理两种类型的操作：

• 1 u，确定大小为 $u$ 的交替组的数量。
• 2 x y，将编号为 $x$ 的瓷砖涂成颜色 $y$。

注意第一块瓷砖和最后一块瓷砖是相邻的。

输入格式

输入的第一行包含两个正整数 $n,q$，分别表示瓷砖和操作的数量。

输入的第二行包含 $n$ 的非负整数 $c_0,c_1,\dots,c_{n-1}$，表示初始时瓷砖的颜色。

接下来的 $q$ 行每行包含两个或三个非负整数：

• 第一个非负整数 $op\in\{1,2\}$，表示操作的类型；
• 若 $op=1$，后面跟着一个正整数 $u$；
• 若 $op=2$，后面跟着两个非负整数 $x,y$。

输出格式

对于每个第 $1$ 类操作，输出一行一个非负整数表示答案。