P17647 [IO 2025 #1] 商人

在游历法鲁姆时，霍妮特遇到了 $n$ 位商人。每位商人恰好出售一种独有的商品，第 $i$ 位商人的商品最初售价为 $a_i$。 霍妮特想知道，购买一段连续商人出售的商品，总共需要花多少钱。但有一个问题：商人们总是在改变售价。具体来说，会依次发生 $q$ 个事件，每个事件属于以下三种类型之一： - `1 i x`：第 $i$ 位商人把商品售价改为 $x$。 - `2 l r`：第 $l$ 至第 $r$ 位商人（包含两端）将各自的商品售价取反。 - `3 l r`：霍妮特打算拜访第 $l$ 至第 $r$ 位商人（包含两端），并想知道购买他们的全部商品所需的总价。 “将售价取反”的过程如下： 1. 商人把当前售价写成恰好 $k$ 位的二进制数（保证 $k$ 位足以表示所有售价）。 2. 如果二进制表示不足 $k$ 位，就在前面补零。 3. 翻转所有二进制位，例如把 `01001` 变为 `10110`。 4. 将得到的二进制数转换回十进制。 请帮助霍妮特回答她的所有询问。

第一行包含两个整数 $n$ 和 $k$，分别表示商人数和售价的二进制位数，满足 $1\le n\le 2\cdot 10^5$、$1\le k\le25$。 第二行包含 $n$ 个整数 $a_i$，表示商品的初始售价，满足 $0\le a_i

对于每个类型为 $3$ 的事件，输出一行，包含对应的区间总价。