题目描述

给定一个长为 $n$ 的序列，支持操作：

• 1 l r x：将区间 $[l,r]$ 的所有元素加 $x$。

• 2 l r ：查询区间 $[l,r]$ 中所有元素异或和的后 $m$ 个二进制位的值。

输入格式

第一行三个正整数 $n,m,q$，表示序列长度，位数，操作数。

第二行 $n$ 个非负整数，表示原始序列 $a_i$。

接下来 $q$ 行，每行若干个非负整数表示一个操作。

输出格式

对于每个 $2$ 操作输出一行，一个非负整数表示答案。

10 2 10
0 1 0 0 1 0 2 2 0 1 
2 3 9
2 1 5
1 9 9 0
1 3 7 2
1 1 6 3
2 1 10
2 6 7
2 3 6
1 3 9 2
1 3 9 3

1
0
3
1
3

提示

【数据范围】
本题共 $10$ 个测试点。

对于测试点 $1 \sim 3$，$1\le n,q \le 1000$；
对于测试点 $4,5$，$1 \le m \le 5$；
对于测试点 $6 \sim 10$，设 $k$ 为测试点编号，有 $m=k$。

对于 $100\%$ 的数据，$1 \le n,q \le 10^5$，$1\le m \le 10$，$0\le a_i,x < 2^m$。

请注意常数优化。