题目背景

题目描述

维护一个长为 $n$，由 $n$ 位二进制数组成的序列 $a$，支持 $m$ 次操作分为两种：

• 1 p val，将 $a_p$ 修改为 $val$。

• 2 p，查询从 $a[1,p]$ 中选出一个子序列，能得到的异或和最大值。

本题强制在线。

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行一个 $n$ 位二进制数，描述 $a$ 序列。

接下来 $m$ 行，每行描述一次操作，要么为 1 p' val' 要么为 2 p'。

记这一次操作前所有询问答案的异或和为 lastans，那么真实的 $p=(p'-1+lastans) \bmod n+1$，真实的 $val=val' \oplus lastans$。

输出格式

对于每次询问操作，输出一个 $n$ 位二进制数表示答案。

5 5
01010
11100
10011
01001
00011
2 5
2 1
1 1 00101
2 5
2 3

11111
11100
11100
11111

10 10
1010101101
0110010101
1100000110
1010010110
0111110111
0111111011
0111101000
1001011011
1100100010
1001000001
1 8 0000010011
2 7
1 4 0010101111
2 4
2 3
1 10 1100001100
2 8
1 5 0100111001
2 5
2 4

1101111110
1111111100
1100111000
1100111000
1110110000
1100111000

提示

Idea：chenxinyang2006，Solution：chenxinyang2006，Code：chenxinyang2006，Data：chenxinyang2006

对于 $100\%$ 的数据：$1 \le n \le 2000,1 \le m \le 4000$，修改操作至多 $n$ 次。$0 \le a_i,val' < 2^n$，$1 \le p' \le n$。