题目描述
我有一个数列 a1,a2,…,an,每个 ai 都是小于 2m 的非负整数。
现在请您实现三种操作,格式说明如下:
- 1 x y w:对于所有 x≤i≤y,将 ai 修改为 aixorw。其中 w 是一个小于 2m 的非负整数。
- 2 x y w:对于所有 x≤i≤y,将 ai 修改为 w。其中 w 是一个小于 2m 的非负整数。
- 3:从 a1,a2,…,an 中选出若干个数,使得选出的数异或和最大。请输出这个最大值。
这里 xor 表示按位异或运算,x1,x2,…,xl 的异或和是指 $x_1 \operatorname{xor} x_2 \operatorname{xor} \dots \operatorname{xor} x_l$。
输入格式
第一行三个正整数 n,m,q。
接下来 n 行为初始时 a1,a2,…,an 的值。
接下来 q 行,每行表示一个操作。操作的格式如前所述。保证 1≤x≤y≤n。
a1,…,an 和 w 均用恰好 m 位的 01 串表示这个数的二进制表示。左边是最高位,右边是最低位,不足 m 位的在左边补 0。
输出格式
对于每个 3 号操作,输出一个 m 位 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
提示
测试点编号 |
n |
m |
q |
特殊限制 |
1 |
=10 |
=1000 |
无 |
2 |
=500 |
=10 |
3 |
=120 |
4 |
=2000 |
=10 |
5 |
=1800 |
1,2 操作中 x=y |
6 |
只有 1,3 操作 |
7 |
只有 2,3 操作 |
8 |
=1500 |
无 |
9 |
=1800 |
10 |
=2000 |