XOR Array Operations and Color Segments Query

You are given an array \(a\) of length \(n = 2^k\) with indices starting from 0. You need to perform \(m\) operations on the array. There are two types of operations:

• Operation 1: Given an integer \(x\), construct a new array \(a'\) such that \(a'_i = a_{i \oplus x}\) for all \(0 \le i < n\) (where \(\oplus\) denotes the bitwise XOR). Then, update \(a\) to be \(a'\).
• Operation 2: Given two indices \(l\) and \(r\), query the subarray between \(l\) and \(r\) (if \(l > r\), swap them first) and report the number of color segments. A color segment is defined as a maximal contiguous subarray where all numbers are equal.

Some of the test cases will be evaluated online.

inputFormat

The first line contains two integers \(k\) and \(m\). Here, \(n = 2^k\) is the length of the array.

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

The following \(m\) lines each describe an operation. Each operation is in one of the following two formats:

• 1 x — Perform Operation 1 with the given \(x\).
• 2 l r — Perform Operation 2 by querying the subarray from index \(l\) to \(r\) (swap \(l\) and \(r\) if \(l > r\)).

outputFormat

For each Operation 2, output a single line containing the number of color segments in the specified subarray.

sample

2 3
1 1 2 2
2 0 3
1 1
2 1 0

2
1