CF2185F.BattleCows

Farmer John is sending a cow to compete in the International Bovine Olympiad, but he's too lazy to write problems for a contest, so he does the next most reasonable thing: a fighting tournament!

Farmer John has $2^n$ cows standing in a line, with the $i$-th cow having a skill level of $a_i$. Each cow starts in a stack containing only itself, and the skill level of the stack is equal to the XOR-sum$^{\text{∗}}$ of the skill levels of all the cows in it. For example, if the stack consists of cows $1, 3, 9$ from bottom to top, then the skill level of the stack is $1 \oplus 3 \oplus 9 = 11$.

The following process repeats until there is only one stack.

• Every stack in an odd position ($1$st, $3$rd, etc.) starts a fight with the stack to its right. For example, the $1$st stack will fight with the $2$nd stack, the $3$rd stack will fight with the $4$th stack, etc.
• The stack with the higher skill level will win the match, with the left-most stack winning in case of a tie.
• The winning stack will jump on top of the losing stack and shift itself over such that there are no gaps left by the defeated stacks.

In order to make this more exciting, Farmer John created $q$ potions, such that the $i$-th potion sets the skill level of the cow who drinks it to $c_i$. Farmer John wants to test his potions on the cows, and so he gives the $i$-th potion to cow $b_i$ and then runs the tournament. For each trial, Farmer John wants to know how many cows are above the cow that was given the potion in the final stack.

Farmer John's potions wear off quickly, so when the tournament ends, the cow that was given the potion will have its skill level return to what it originally was. In other words, all queries are independent.

$^{\text{∗}}$The XOR-sum of an array $x_1, x_2, \ldots, x_y$ is equal to $x_1 \oplus x_2 \oplus x_3 \ldots x_{y-1} \oplus x_y$ where $\oplus$ denotes the bitwise XOR operation.

农夫约翰要派一头奶牛参加国际奶牛奥林匹克竞赛，但他懒得出题，于是选择了次合理的选择：举办一场格斗锦标赛！

农夫约翰有 $2^n$ 头奶牛排成一列，其中第 $i$ 头奶牛的技能值为 $a_i$。每头奶牛初始时各自构成一个仅含自身的栈，该栈的技能值定义为栈中所有奶牛技能值的异或和$^{\text{∗}}$。例如，若某栈从底到顶依次包含奶牛 $1, 3, 9$，则该栈的技能值为 $1 \oplus 3 \oplus 9 = 11$。

以下过程不断重复，直至只剩下一个栈：

• 所有处于奇数位置（第 $1$ 个、第 $3$ 个等）的栈，将与它右侧相邻的栈进行格斗。例如，第 $1$ 个栈与第 $2$ 个栈格斗，第 $3$ 个栈与第 $4$ 个栈格斗，依此类推。
• 技能值更高的栈赢得该场格斗；若技能值相等，则左侧的栈获胜。
• 获胜的栈将跳至失败栈的顶部，并向左移动以填补被击败栈留下的空位（即保持栈序列连续无间隙）。

为了增加比赛的观赏性，农夫约翰制作了 $q$ 种药剂，其中第 $i$ 种药剂可将饮用它的奶牛的技能值设为 $c_i$。农夫约翰想在奶牛身上测试这些药剂，因此他将第 $i$ 种药剂给予第 $b_i$ 头奶牛，然后立即运行锦标赛。对于每次测试，农夫约翰想知道：在最终形成的唯一栈中，被给予药剂的那头奶牛上方有多少头奶牛。

农夫约翰的药剂效果持续时间很短，因此锦标赛结束后，被给予药剂的奶牛技能值会恢复为其原始值。换言之，所有查询彼此独立。

$^{\text{∗}}$ 数组 $x_1, x_2, \ldots, x_y$ 的异或和定义为 $x_1 \oplus x_2 \oplus x_3 \ldots \oplus x_{y-1} \oplus x_y$，其中 $\oplus$ 表示按位异或运算。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $q$ ($1 \le n \le 18$, $1 \le q \le 2 \cdot 10^5$) — where $2^n$ is equal to the number of cows in the tournament and $q$ is the number of potions.

The second line contains $2^n$ integers $a_1, a_2, \ldots, a_{2^n}$ ($1 \le a_i \le 2^{30}$) — the skill levels of the cows.

The next $q$ lines contain two integers $b_i$ and $c_i$ ($1 \le b_i \le 2^n$, $1 \le c_i \le 2^{30}$) — the index of the cow that is given the potion and the new skill level of the cow.

It is guaranteed that the sum of $2^n$ over all test cases does not exceed $2^{18} = 262144$ and that the sum of $q$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 18$，$1 \le q \le 2 \cdot 10^5$），其中 $2^n$ 表示锦标赛中奶牛的数量，$q$ 表示药水的数量。

第二行包含 $2^n$ 个整数 $a_1, a_2, \ldots, a_{2^n}$（$1 \le a_i \le 2^{30}$），表示各头奶牛的技能等级。

接下来的 $q$ 行每行包含两个整数 $b_i$ 和 $c_i$（$1 \le b_i \le 2^n$，$1 \le c_i \le 2^{30}$），分别表示被给予药水的奶牛的索引及其新的技能等级。

保证所有测试用例中 $2^n$ 的总和不超过 $2^{18} = 262144$，且所有测试用例中 $q$ 的总和不超过 $2 \cdot 10^5$。

For each trial, output how many cows are above the cow that was given the potion in the final line.

对于每次试验，输出在最后一行给出药剂的奶牛上方的奶牛数量。

For the first round of the first test case, the skill levels of the cows don't change, and the matches go as follows:

• Cows $1$ and $2$ fight. Since cow $2$'s skill level is higher than cow $1$'s skill level, cow $2$ wins the fight, so its stack has cows $1, 2$ in that order, and the stack's skill level is now $3 \oplus 1 = 2$.
• Cows $3$ and $4$ fight. Since cow $4$'s skill level is higher than cow $3$'s skill level, cow $4$ wins the fight, so its stack has cows $3, 4$ in that order, and the stack's skill level is now $7 \oplus 5 = 2$.
• The two remaining stacks fight. Since the first stack's skill level is equal to the second stack's skill level, the first stack wins the fight, since its index is lower than the second stack's, so the final stack has cows $3, 4, 1, 2$ in that order, and its skill level is now $2 \oplus 2 = 0$.

Since we gave the potion to cow $1$, our answer is $1$, since there is one cow above cow $1$.

A visualization of the round is shown below.

For the second round of the first test case, cow $4$ 's skill level is now $8$, and the matches go as follows:

• Cows $1$ and $2$ fight. Since cow $2$'s skill level is higher than cow $1$'s skill level, cow $2$ wins the fight, so its stack has cows $1, 2$ in that order, and the stack's skill level is now $3 \oplus 1 = 2$.
• Cows $3$ and $4$ fight. Since cow $4$'s skill level is higher than cow $3$'s skill level, cow $4$ wins the fight, so its stack has cows $3, 4$ in that order, and the stack's skill level is now $8 \oplus 5 = 13$.
• The two remaining stacks fight. Since the second stack's skill level is higher than the first stack's skill level, the second stack wins the fight, so the final stack has cows $1, 2, 3, 4$ in that order, and its skill level is now $2 \oplus 13 = 15$.

Since we gave the potion to cow $4$, our answer is $0$, since there are no cows above cow $4$.

对于第一个测试用例的第一轮，奶牛的技能等级不发生变化，比赛过程如下：

• 奶牛 $1$ 与奶牛 $2$ 对战。由于奶牛 $2$ 的技能等级高于奶牛 $1$ 的技能等级，奶牛 $2$ 获胜，因此其栈中奶牛顺序为 $1, 2$，该栈的技能等级变为 $3 \oplus 1 = 2$。
• 奶牛 $3$ 与奶牛 $4$ 对战。由于奶牛 $4$ 的技能等级高于奶牛 $3$ 的技能等级，奶牛 $4$ 获胜，因此其栈中奶牛顺序为 $3, 4$，该栈的技能等级变为 $7 \oplus 5 = 2$。
• 剩余的两个栈对战。由于第一个栈的技能等级等于第二个栈的技能等级，而第一个栈的索引更小，因此第一个栈获胜，最终栈中奶牛顺序为 $3, 4, 1, 2$，其技能等级变为 $2 \oplus 2 = 0$。

由于我们将药水给了奶牛 $1$，答案为 $1$，因为奶牛 $1$ 上方有 $1$ 头奶牛。

本回合的可视化图示如下所示。

对于第一个测试用例的第二轮，奶牛 $4$ 的技能等级变为 $8$，比赛过程如下：

• 奶牛 $1$ 与奶牛 $2$ 对战。由于奶牛 $2$ 的技能等级高于奶牛 $1$ 的技能等级，奶牛 $2$ 获胜，因此其栈中奶牛顺序为 $1, 2$，该栈的技能等级变为 $3 \oplus 1 = 2$。
• 奶牛 $3$ 与奶牛 $4$ 对战。由于奶牛 $4$ 的技能等级高于奶牛 $3$ 的技能等级，奶牛 $4$ 获胜，因此其栈中奶牛顺序为 $3, 4$，该栈的技能等级变为 $8 \oplus 5 = 13$。
• 剩余的两个栈对战。由于第二个栈的技能等级高于第一个栈的技能等级，第二个栈获胜，因此最终栈中奶牛顺序为 $1, 2, 3, 4$，其技能等级变为 $2 \oplus 13 = 15$。

由于我们将药水给了奶牛 $4$，答案为 $0$，因为奶牛 $4$ 上方没有奶牛。