P12829 「DLESS-2」XOR and Inversion

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.

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.

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

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