当前没有测试数据。

5.二进制

题目描述

给定一个长度为$n$的整数数列$a$和$q$次操作：

• 修改操作：$1$ $x$ $y$，表示将$a[x]$的值改为$y$；
• 询问操作：$2$ $x$ $y$，表示询问$\sum_{i=1}^{n}\left(\left(a_{i}+x\right)\ \text{and}\ y\right)$的值。

输入格式

第一行包含两个整数$n$，$q$。

第二行包含$n$个整数$a[i]$。

之后$q$行每行包含三个整数$opt$，$x$，$y$。

输出格式

对于每一个询问，输出一行一个整数，表示答案。

数据范围与提示

• 对于$40\%$的数据，$n$，$q \leq 5000$；
• 对于另外$20\%$的数据，所有询问满足$x = 0$；
• 对于$100\%$的数据，$1 \leq n,q \leq 10^{5}$，$0 \leq a_i,x,y < 2^{20}$。

样例

6 6
8 9 1 13 9 3
1 4 5
2 6 9
1 3 7
2 7 7
1 6 1
2 11 13

45
19
21