Description

You are given a permutation $p$ of integers from $0$ to $2^n-1$. You need to perform $q$ operations. Each operation is one of the following two types:

• 1 x: Every element $p_i$ in the permutation is replaced by $p_i \oplus x$.
• 2 x: The permutation is reordered. For every $i$, the new element at index $i$ is the element that was previously at index $i \oplus x$.

Here, $\oplus$ denotes the bitwise XOR operation. The effects of the operations are cumulative.

After each operation, you need to find the total number of inversions in the current permutation.

Input Format

The input consists of multiple test cases. The first line contains a single positive integer $T$, representing the number of test cases.

For each test case:

The first line contains two integers $n$ and $q$.

The second line contains $2^n$ integers, representing the permutation $p$.

The next $q$ lines each contain two integers, representing an operation in the format described above.

Output Format

After each operation, output a single line with a single integer, which is the answer.

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

Hint

For all test data, it is guaranteed that:

• $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$

This problem uses bundled tests. The subtasks are described as follows:

The memory limit for Subtask 11 is 128MB; for all other subtasks, it is 1GB.

Special Property A: Only type 1 operations are given.

Special Property B: Only type 2 operations are given.