题目描述

给定 $0\sim 2^n-1$ 的排列 $p$，下标从 $0$ 开始，$q$ 次操作，每次操作形如以下两种中的一种：

• 1 x: 将排列中的每个元素 $p_i$ 替换为 $p_i \oplus x$。
• 2 x: 重新排列 $p$。对于每一个下标 $i$，操作后下标 $i$ 处的新元素是操作前下标 $i \oplus x$ 处的元素。

其中 $\oplus$ 表示按位异或运算。操作有后效性。

每次操作后，求出整个序列的逆序对数。

输入格式

本题有多组测试数据，第一行输入一个正整数 $T$，代表数据组数。

对于每组数据：

第一行输入两个数 $n,q$。

第二行输入 $2^n$ 个数，代表排列 $p$。

接下来 $q$ 行，每行两个数，代表一次操作，格式如题目描述所示。

输出格式

在每次操作后，输出一行一个数，代表答案。

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

18
18
5
5
3
3
3
1
5

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

4
4
6
6
21
21
21
11
19

1
5 9
21 26 25 9 11 15 4 5 20 14 3 10 23 27 19 7 18 6 29 28 16 17 12 30 22 8 24 2 1 31 0 13 
2 21
1 16
1 15
2 0
2 10
2 24
2 11
1 30
1 21

269
225
227
227
259
257
267
223
275

1
0 4
0
1 0
2 0
2 0
1 0

0
0
0
0

提示

对于所有数据，保证：

• $1\le T\le 10^5$
• $1\le 2^n,\sum 2^n\le 2^{20}$
• $1\le q,\sum q\le 10^6$
• $0\le x<2^n$

本题采用打包测试，各子任务描述如下：

其中，除第 $11$ 个子任务空间限制为 128MB 外，其余子任务空间限制为 1GB。

特殊性质 A：只有第一种操作。

特殊性质 B：只有第二种操作。