Problem Description

Given an array \( a \) of length \( n = 2^k \), indexed from 0, maintain \( m \) operations:

1. Operation 1: Given \( x \), let array \( a' \) satisfy \( a'_i = a_{i \oplus x} \), where \( \oplus \) denotes the bitwise XOR operation. Modify \( a \) to \( a' \).
2. Operation 2: Given \( l, r \), query the number of color segments in the subarray of \( a \) with indices between \( l \) and \( r \). Note that \( l \le r \) is not guaranteed; if \( l > r \), swap \( l \) and \( r \).

A maximally long subarray where all elements are equal is called a color segment.

Some test cases require online processing.

Input Format

The first line contains three integers \( T, k, m \), where \( T \in \{ 0, 1 \} \) determines whether online processing is required.

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

The next \( m \) lines describe each operation. The first integer \( \mathit{op} \) indicates the operation type.

• If \( \mathit{op} = 1 \), it is Operation 1, followed by an integer \( x' \) where \( x = x' \oplus (T \times \mathit{lst}) \).
• If \( \mathit{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}) \). Note that \( l \le r \) is not guaranteed; if \( l > r \), swap \( l \) and \( r \).
• \( \mathit{lst} \) represents the answer to the last query. If there has been no previous query, \( \mathit{lst} = 0 \).

Output Format

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

5
4

Input Sample #2

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

Output Sample #2

5
4

Input Sample #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 Sample #3

5
7
4
7
9
5
7
2
11

Notes/Hints

Sample Explanation #1

This sample 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.

Sample Explanation #2

This sample, except for the online requirement, is identical to Sample #1.

Data Range

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 batched testing.

• Subtask 1 (15 points): \( T = 1 \), \( k \le 10 \), \( m \le 10^3 \).
• Subtask 2 (15 points): \( T = 1 \), no Operation 1.
• 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; only by passing the first four subtasks can you attempt to score in this subtask.

见题面 Input 部分

见题面 Output 部分