#P11731. [集训队互测 2015] 最大异或和

[集训队互测 2015] 最大异或和

题目描述

我有一个数列 a1,a2,,ana_1, a_2, \dots, a_n,每个 aia_i 都是小于 2m2^m 的非负整数。

现在请您实现三种操作,格式说明如下:

  • 11 xx yy ww:对于所有 xiyx \leq i \leq y,将 aia_i 修改为 aixorwa_i \operatorname{xor} w。其中 ww 是一个小于 2m2^m 的非负整数。
  • 22 xx yy ww:对于所有 xiyx \leq i \leq y,将 aia_i 修改为 ww。其中 ww 是一个小于 2m2^m 的非负整数。
  • 33:从 a1,a2,,ana_1, a_2, \dots, a_n 中选出若干个数,使得选出的数异或和最大。请输出这个最大值。

这里 xor\operatorname{xor} 表示按位异或运算,x1,x2,,xlx_1, x_2, \dots, x_l 的异或和是指 $x_1 \operatorname{xor} x_2 \operatorname{xor} \dots \operatorname{xor} x_l$。

输入格式

第一行三个正整数 n,m,qn,m,q

接下来 nn 行为初始时 a1,a2,,ana_1, a_2, \dots, a_n 的值。

接下来 qq 行,每行表示一个操作。操作的格式如前所述。保证 1xyn1 \leq x \leq y \leq n

a1,,ana_1, \dots, a_nww 均用恰好 mm 位的 01 串表示这个数的二进制表示。左边是最高位,右边是最低位,不足 mm 位的在左边补 00

输出格式

对于每个 33 号操作,输出一个 mm 位 01 串表示答案的二进制表示。

3 4 7
0000
0011
0110
3
1 2 3 0010
3
2 1 2 0010
3
2 1 3 0000
3
0110
0101
0110
0000

提示

测试点编号 nn mm qq 特殊限制
11 =10= 10 =1000= 1000
22 =500= 500 =10= 10
33 =120= 120
44 =2000= 2000 =10= 10
55 =1800= 1800 1,21, 2 操作中 x=yx = y
66 只有 1,31, 3 操作
77 只有 2,32, 3 操作
88 =1500= 1500
99 =1800= 1800
1010 =2000= 2000