$\newcommand\xor{\mathbin{\mathrm{xor}}}$
我有一个数列 $a_1, a_2, \dots, a_n$，每个 $a_i$ 都是小于 $2^m$ 的非负整数。
现在请您实现三种操作，格式说明如下：
- $1$ $x$ $y$ $w$：对于所有 $x \leq i \leq y$，将 $a_i$ 修改为 $a_i \xor w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
- $2$ $x$ $y$ $w$：对于所有 $x \leq i \leq y$，将 $a_i$ 修改为 $w$。其中 $w$ 是一个小于 $2^m$ 的非负整数。
- $3$：从 $a_1, a_2, \dots, a_n$ 中选出若干个数，使得选出的数异或和最大。请输出这个最大值。
这里 $\xor$ 表示按位异或运算，$x_1, x_2, \dots, x_l$ 的异或和是指 $x_1 \xor x_2 \xor \dots \xor x_l$。
输入格式
第一行三个正整数 $n,m,q$。
接下来 $n$ 行为初始时 $a_1, a_2, \dots, a_n$ 的值。
接下来 $q$ 行，每行表示一个操作。操作的格式如前所述。保证 $1 \leq x \leq y \leq n$。
$a_1, \dots, a_n$ 和 $w$ 均用恰好 $m$ 位的 01 串表示这个数的二进制表示。左边是最高位，右边是最低位，不足 $m$ 位的在左边补 $0$。
输出格式
对于每个 $3$ 号操作，输出一个 $m$ 位 01 串表示答案的二进制表示。
样例一
input
3 4 7 0000 0011 0110 3 1 2 3 0010 3 2 1 2 0010 3 2 1 3 0000 3
output
0110 0101 0110 0000
限制与约定
| 测试点编号 | $n$ | $m$ | $q$ | 特殊限制 |
|---|---|---|---|---|
| 1 | $= 10$ | $= 10$ | $= 1000$ | 无 |
| 2 | $= 500$ | $= 500$ | $= 10$ | |
| 3 | $= 120$ | $= 120$ | $= 120$ | |
| 4 | $= 2000$ | $= 2000$ | $= 10$ | |
| 5 | $= 1800$ | $= 1800$ | $= 1800$ | $1, 2$ 操作中 $x = y$ |
| 6 | 只有 $1, 3$ 操作 | |||
| 7 | 只有 $2, 3$ 操作 | |||
| 8 | $=1500$ | $=1500$ | $=1500$ | 无 |
| 9 | $=1800$ | $=1800$ | $=1800$ | |
| 10 | $=2000$ | $=2000$ | $=2000$ |
时间限制：$2\texttt{s}$
空间限制：$256\texttt{MB}$
来源
中国国家集训队互测2015 - By 金策