# 纳米电脑主机

- 参考时间限制：0.5 秒（参考环境：[评测环境与性能](../../../docs/评测环境与性能.md)；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：64 MB

## 背景故事

帝国研究员用纳米电脑主机分析无人机的升级方案。研究记录是一列非负整数，每种连续的研究组合都有一个异或值。研究员会修改单条记录，也会查询一段记录内所有连续组合的异或值之和。请帮助主机及时回答。

## 形式化问题描述

维护长度为 $n$ 的非负整数数组 $a_1,\ldots,a_n$ ，依次处理 $q$ 个操作：

- `1 l r` ：查询所有满足 $l\le i\le j\le r$ 的非空子区间 $[i,j]$ 的异或值之和，即

$$\sum_{i=l}^{r}\sum_{j=i}^{r}(a_i\oplus a_{i+1}\oplus\cdots\oplus a_j)$$

- `2 p v` ：把 $a_p$ 赋值为 $v$ ，不是加上 $v$ .

其中 $\oplus$ 表示按位异或。外层求和使用普通整数加法，不再异或，也不取模。每次查询使用当时的数组。

## 输入格式

第一行 $n,q$ .第二行 $n$ 个整数表示初始数组。之后 $q$ 行按上述格式给出操作。

## 输出格式

每次操作 `1` 输出一行一个整数。若没有查询，则不输出任何内容。

## 样例 1

### 输入

```text
10 10
10 3 8 2 6 10 7 6 1 8
1 2 4
2 10 8
1 1 3
2 8 4
2 6 8
2 2 10
1 9 9
2 3 7
1 6 6
1 8 8
```

### 输出

```text
43
42
1
8
4
```

### 解释

第一次查询的数组为 $[3,8,2]$ ，六个子区间的异或值为 $3,8,2,11,10,9$ ，总和为 $43$ .

## 样例 2

### 输入

```text
2 4
65536 65536
1 1 2
2 1 0
1 1 2
1 1 1
```

### 输出

```text
131072
131072
0
```

### 解释

数值 $65536$ 的第 $16$ 位为 $1$ ，必须计入。长度为二的子区间在修改前异或值为 $0$ ，修改后为 $65536$ .

## 数据范围与保证

- $1\le n,q\le100000$ .
- 初始值和赋值参数均满足 $0\le a_i,v\le65536$ .
- $1\le l\le r\le n$ ，$1\le p\le n$ .

### 数据分组

| 分值比例 | 额外条件 |
| --- | --- |
| 100% | 无额外条件 |