题目描述

对于正整数 $b$，定义 $R(b)=\lfloor\frac{2^{2\lceil b/2\rceil}}{3}\rfloor$。

对于一个长度为 $2^b$ 的下标从 $\bm0$ 开始的序列 $a$，定义其权值 $\operatorname{val}(a)$ 为其和最大的子序列，其中如果 $i,j$ 满足 $|(i\oplus R(b))-(j\oplus R(b))|=1$ 则 $a_i,a_j$ 两个位置不能同时出现在子序列中。

Saturday 给你一个长度为 $n$ 的整数序列 $a$，有 $q$ 次询问或操作：

• 1 x v，把 $a_x$ 改为 $v$。
• 2 l r，求 $a$ 的子段 $a_l,a_{l+1},\cdots,a_r$ 的权值（注意计算权值的时候要将下标从 $0$ 重新编号）。

对于所有 2 操作，保证 $r-l+1$ 是 $2$ 的整数次幂。

输入格式

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

第二行 $n$ 个正整数描述序列 $a$。

后 $q$ 行每行三个正整数描述一次询问或操作（含义见题目描述）。

输出格式

若干行，每行回答一组询问。

样例 #1

样例输入 #1

8 8
1 2 3 4 5 6 7 8
2 1 2
2 1 4
1 2 7
1 3 8
2 1 8
2 2 5
1 8 1
2 5 8

样例输出 #1

2
6
29
13
13

数据范围

本题采用捆绑测试。

数据范围：

• Subtask 1 (10pts)：$n\le 20$，$q\le 10$。
• Subtask 2 (20pts)：$n,q\le 10^3$。
• Subtask 3 (20pts)：保证没有 1 操作。
• Subtask 4 (50pts)：无特殊限制。

对于全部数据，$1\le n,q\le2\times10^5$，$|a_i|\le 100$。