✿(。◕ᴗ◕。)✿

Given an array $a$ of length $n=2^k$ with 0-based indexing, maintain $m$ operations:

1. Operation 1: Given $x$, let the sequence $a'$ satisfy $a'_i=a_{i\oplus x}$, and update $a$ to $a'$. Here, $\oplus$ denotes the bitwise XOR operation.
2. Operation 2: Given $l, r$, query the number of color segments in the subarray of $a$ with indices between $l$ and $r$. It is not guaranteed that $l \le r$; if $l > r$, please swap $l$ and $r$ yourself.

A color segment is defined as a maximal contiguous subarray where all elements are equal.

Some test cases require the solution to be online.

Input

The first line contains three integers $T, k, m$, where $T \in \{ 0, 1 \}$ is a parameter determining whether the solution must be online.

The second line contains $n$ integers $a_0, \ldots, a_{n-1}$.

The next $m$ lines each contain two or three integers describing an operation. The first integer $\mathit{op}$ indicates the operation type.

• If $op=1$, it is Operation 1, followed by an integer $x'$, where $x=x'\oplus(T\times \mathit{lst})$.
• If $op=2$, it is Operation 2, followed by two integers $l', r'$, where $l=l'\oplus(T\times \mathit{lst})$ and $r=r'\oplus(T\times \mathit{lst})$. It is not guaranteed that $l \le r$; if $l > r$, please swap $l$ and $r$ yourself.
• Here, $\mathit{lst}$ represents the answer to the previous query. Specifically, if there were no previous query operations, $\mathit{lst}=0$.

Output

Output several lines, each containing an integer representing the answer to each query in order.

Examples

Input 1

0 3 3
1 2 1 3 2 4 5 1
2 1 5
1 3
2 5 1

Output 1

5
4

Note 1

This example allows offline processing.

Initially, $a=[1,2,1,3,2,4,5,1]$.

The subarray of $a$ with indices between $1$ and $5$ is $[2,1,3,2,4]$, which has $5$ color segments.

After the rearrangement operation, $a=[3,1,2,1,1,5,4,2]$.

The subarray of $a$ with indices between $5$ and $1$ is $[1,2,1,1,5]$, which has $4$ color segments.

Input 2

1 3 3
1 2 1 3 2 4 5 1
2 1 5
1 6
2 0 4

Output 2

5
4

Note 2

This example is identical to Example 1, except that it requires an online solution.

Input 3

1 4 16
12 9 5 9 12 12 9 12 9 16 5 9 12 16 9 5
2 0 4
1 15
2 14 0
1 15
2 6 0
2 4 14
1 0
1 14
2 4 10
2 6 3
1 7
2 4 13
1 3
1 3
2 4 3
2 15 2

Output 3

5
7
4
7
9
5
7
2
11

Constraints

For all test data, $T \in \{ 0, 1 \}$, $0\le k\le 18$, $n=2^k$, $1\le m\le 2\times 10^5$, $1\le a_i\le n$, $\mathit{op} \in \{ 1, 2 \}$, $0\le x,l,r < n$.

This problem uses bundled testing.

• Subtask 1 (15 points): $T=1$, $k\le 10$, $m\le 10^3$.
• Subtask 2 (15 points): $T=1$, no Operation 1 exists.
• Subtask 3 (20 points): $T=1$, for all Operation 2, either $l=0, r=n-1$ or $l=n-1, r=0$.
• Subtask 4 (20 points): $T=0$.
• Subtask 5 (30 points): $T=1$.

Note: Subtask 5 depends on the first four subtasks; you can only attempt to earn points for this subtask after passing the first four subtasks.