该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

昆明的中午

题目描述

$atzk$、 $wqsing$、 $sad$ 在昆明打铁之后闲着没事正在打牌

游戏规则是这样的

给你一个长度为 $n$ 的牌序列，每张牌有一个值 $v_i$

有两种操作

• $1\ x\ v$ 表示将位置 $x$ 的值修改为 $v$
• $2\ l\ r$ 表示询问 $\sum_{i = l}^{r}\sum_{j = i}^{r}f(i, j)$，其中 $f(i, j) = a_i\oplus a_{i + 1} \oplus ... \oplus a_j，\oplus$ 表示 xor

输入格式

第一行 $n, m$

第二行 $n$ 个数，表示初始牌序列

接下来 $m$ 行，表示 $m$ 种操作 $1\ x\ v /\ 2\ l\ r$

$0 \le v_i, v \le 1023, 1 \le x \le n, 1 \le l \le r \le n ， 1 \le n,m \le 10^6 $

输出格式

对于每一个询问，一行输出一个值

样例 #1

样例输入 #1

10 5
14 18 11 8 1 7 18 17 20 14 
2 1 6
2 4 7
1 2 3
1 5 4
2 4 5

样例输出 #1

316
132
24

样例 #2

样例输入 #2

10 5
1 11 2 18 13 12 2 12 10 9 
2 6 10
2 2 10
1 2 19
2 1 3
1 8 0

样例输出 #2

125
696
73

说明

请注意本题已开大时限