I have a sequence $a_1, a_2, \dots, a_n$, where each $a_i$ is a non-negative integer less than $2^m$.

Please implement three types of operations as described below:

• $1$ $x$ $y$ $w$: For all $x \leq i \leq y$, update $a_i$ to $a_i \xor w$, where $w$ is a non-negative integer less than $2^m$.
• $2$ $x$ $y$ $w$: For all $x \leq i \leq y$, update $a_i$ to $w$, where $w$ is a non-negative integer less than $2^m$.
• $3$: Choose a subset of numbers from $a_1, a_2, \dots, a_n$ such that their XOR sum is maximized. Output this maximum value.

Here, $\xor$ denotes the bitwise XOR operation, and the XOR sum of $x_1, x_2, \dots, x_l$ is defined as $x_1 \xor x_2 \xor \dots \xor x_l$.

Input

The first line contains three positive integers $n, m, q$.

The next $n$ lines contain the initial values of $a_1, a_2, \dots, a_n$.

The next $q$ lines each describe an operation. The format is as described above. It is guaranteed that $1 \leq x \leq y \leq n$.

$a_1, \dots, a_n$ and $w$ are all represented as $m$-bit binary strings. The leftmost bit is the most significant bit, and the rightmost bit is the least significant bit. If the number has fewer than $m$ bits, it is padded with $0$s on the left.

Output

For each operation of type $3$, output an $m$-bit binary string representing the binary representation of the answer.

Examples

Input 1

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

Output 1

0110
0101
0110
0000

Constraints