F. BattleCows
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

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

Output

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

Example
Input
4
2 2
1 3 5 7
1 1
4 8
1 2
1 3
1 4
1 2
3 4
1 8 3 10 2 5 7 1
5 3
8 12
1 9
2 1
2 1
1 2 3 4
3 1
Output
1
0
0
1
5
0
2
3
1
Note

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