Maintain a sequence $a$ of length $n$, consisting of $n$-bit binary numbers. Support $m$ operations of two types:

• 1 p val: Update $a_p$ to $val$.
• 2 p: Query the maximum XOR sum obtainable from a subsequence of $a[1, p]$.

This problem is online.

Input

The first line contains two integers $n$ and $m$.

The next $n$ lines each contain an $n$-bit binary number, describing the sequence $a$.

The next $m$ lines each describe an operation, either 1 p' val' or 2 p'.

Let lastans be the XOR sum of the answers to all previous queries (initially 0). The actual $p$ is $(p'-1+lastans) \bmod n+1$, and the actual $val$ is $val' \oplus lastans$.

Output

For each query operation, output an $n$-bit binary number representing the answer.

Examples

Input 1

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

Output 1

11111
11100
11100
11111

Input 2

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

Output 2

1101111110
1111111100
1100111000
1100111000
1110110000
1100111000

Subtasks

Idea: chenxinyang2006, Solution: chenxinyang2006, Code: chenxinyang2006, Data: chenxinyang2006

For $100\%$ of the data: $1 \le n \le 2000, 1 \le m \le 4000$, with at most $n$ update operations. $0 \le a_i, val' < 2^n$, $1 \le p' \le n$.