题目背景

✿(。◕ᴗ◕。)✿

题目描述

给定一个长度为 $n=2^k$ 的数组 $a$，下标从 $0$ 开始，维护 $m$ 次操作：

1. 操作一：给定 $x$，设数列 $a'$ 满足 $a'_i=a_{i\oplus x}$，将 $a$ 修改为 $a'$。其中 $\oplus$ 表示按位异或运算。
2. 操作二：给定 $l,r$，查询 $a$ 的下标在 $l,r$ 之间的子数组有多少颜色段。不保证 $\boldsymbol {l\le r}$，若 $\boldsymbol{l > r}$，请自行交换 $\boldsymbol{l,r}$。

其中，一个极长的所有数都相等的子数组称为一个颜色段。

部分测试点要求强制在线。

输入格式

第一行三个整数 $T,k,m$，其中 $T \in \{ 0, 1 \}$ 为决定是否强制在线的参数。

第二行 $n$ 个整数 $a_0, \ldots, a_{n-1}$。

接下来 $m$ 行，每行两或三个整数，描述一次操作。第一个整数 $\mathit{op}$ 表示操作类型。

• 若 $op=1$，为操作一，接下来一个整数 $x'$，满足 $x=x'\oplus(T\times \mathit{lst})$。
• 若 $op=2$，为操作二，接下来两个整数 $l',r'$，满足 $l=l'\oplus(T\times \mathit{lst})$，$r=r'\oplus(T\times \mathit{lst})$。不保证 $\boldsymbol{l \le r}$，若 $\boldsymbol{l > r}$，请自行交换 $\boldsymbol{l, r}$。
• 其中 $\mathit{lst}$ 表示上次询问的答案。特别地，如果此前没有询问操作，则 $\mathit{lst}=0$。

输出格式

输出若干行，每行包含一个整数，依次表示每个询问的答案。

样例 1 输入

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

样例 1 输出

5
4

样例 1 解释

此样例允许离线。

初始时 $a=[1,2,1,3,2,4,5,1]$。

$a$ 的下标在 $1,5$ 之间的子数组为 $[2,1,3,2,4]$，它的颜色段数为 $5$。

进行重排操作后，$a=[3,1,2,1,1,5,4,2]$。

$a$ 的下标在 $5,1$ 之间的子数组为 $[1,2,1,1,5]$，它的颜色段数为 $4$。

样例 2 输入

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

样例 2 输出

5
4

样例 2 解释

此样例除强制在线外，与样例 1 完全一致。

样例 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

样例 3 输出

5
7
4
7
9
5
7
2
11

数据范围

对于所有测试数据，$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$。

本题采用捆绑测试。

• Subtask 1（15 points）：$T=1$，$k\le 10$，$m\le 10^3$。
• Subtask 2（15 points）：$T=1$，不存在操作一。
• Subtask 3（20 points）：$T=1$，对于所有操作二，要么 $l=0,r=n-1$，要么 $l=n-1,r=0$。
• Subtask 4（20 points）：$T=0$。
• Subtask 5（30 points）：$T=1$。

注意：Subtask 5 依赖前四个 Subtask，只有通过前四个 Subtask 才能尝试获得该 Subtask 的分数。