题目描述

张三和李四在玩游戏。游戏规则是这样的：

在他们面前有一个棋盘，棋盘是一个由 $n$ 个节点和 $n$ 条边构成的环，边有边权。初始时，一枚棋子被放置在某个节点上。张三和李四轮流移动棋子，张三为先手，无法移动者败。每次移动时，必须选择棋子当前所在节点的某个相邻点（即有边相连的点），沿着边将棋子移动到这个相邻点去，并将边权减少任意正整数。需要注意的是，边权不允许被减小到负数。

张三想让你算算，对于给定的棋盘，有多少种初始棋子的摆放方式能使得他有必胜策略。

现在你有一个长为 $m$ 的序列 $a_1,a_2,\dots,a_m$，你需要完成 $q$ 次操作。每次操作形式为如下之一：

• 1 x y 表示将 $a_x$ 赋值为 $y$；
• 2 l r 表示查询如果棋盘上共 $(r-l+1)$ 个节点，且边权以顺时针方向分别为 $a_l,a_{l+1},\dots,a_r$，那么这样一盘游戏共有多少个不同的初始棋子位置可以让张三有必胜策略。

输入格式

输入共 $m+2$ 行。

第一行两个正整数 $m,q$。

第二行 $m$ 个整数，第 $i$ 个数为 $a_i$。

接下来 $q$ 行，每行三个整数，格式如题面所述。

输出格式

输出若干行，每行一个非负整数，表示一次询问的答案。

6 7
0 1 0 2 3 0
2 1 6
1 1 1
2 1 6
2 4 5
1 4 3
2 3 5
2 4 5

3
2
2
1
0

见选手目录下的 ring/ring2.in 与 ring/ring2.ans。

见选手目录下的 ring/ring2.in 与 ring/ring2.ans。

提示

子任务

对于所有测试数据，保证 $1 \le m,q \le 3 \times 10^5$，$1 \le l \le r \le m$，$1\le x \le m$，$0 \le y,a_i \le 10^6$。

特殊性质 A：保证 $0 \le y,a_i \le 1$。

特殊性质 B：保证所有询问满足 $l=1$，$r=m$。

特殊性质 C：保证没有修改操作。