题目描述

在游历法鲁姆时，霍妮特遇到了 $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<2^k$。

第三行包含一个整数 $q$，表示事件数，满足 $1\le q\le2\cdot10^5$。

接下来 $q$ 行，每行按题目描述中的格式给出一个事件：先给出事件类型，再给出相应参数。参数满足 $1\le i,l,r\le n$、$0\le x<2^k$。

输出格式

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

5 3
1 2 3 4 5
7
1 2 7
3 1 5
3 2 2
2 2 2
3 2 2
2 1 5
3 1 5

20
7
0
22