题目描述

Farmer John 要派一头奶牛参加国际牛类奥林匹克，但他懒得写题，于是举办了一场战斗锦标赛。

有 $2^n$ 头奶牛排成一行，第 $i$ 头奶牛的技能值为 $a_i$。每头奶牛初始时单独成一个栈，栈的技能值等于栈中所有奶牛技能值的异或和。例如，如果一个栈从下到上包含技能值为 $1,3,9$ 的奶牛，则该栈技能值为 $1\oplus 3\oplus 9=11$。

重复以下过程，直到只剩一个栈：

• 所有奇数位置的栈（第 $1$、第 $3$ 个等）与其右侧相邻栈战斗。
• 技能值更高的栈获胜；若平局，则位置更靠左的栈获胜。
• 获胜栈跳到失败栈上方，随后所有栈向左靠拢，不留下空位。

为了让比赛更有趣，Farmer John 准备了 $q$ 瓶药水。第 $i$ 瓶药水会把第 $b_i$ 头奶牛的技能值改为 $c_i$。每次试验中，他把第 $i$ 瓶药水给第 $b_i$ 头奶牛，然后运行锦标赛。对于每次试验，请输出最终栈中有多少头奶牛位于喝药水的奶牛上方。

药水很快失效，所以每次询问互相独立。

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含两个整数 $n,q$，其中 $2^n$ 为奶牛数量，$q$ 为药水数量。

第二行包含 $2^n$ 个整数 $a_1,a_2,\ldots,a_{2^n}$。

接下来 $q$ 行，每行包含两个整数 $b_i,c_i$，表示喝药水的奶牛编号和新的技能值。

保证所有测试数据的 $2^n$ 之和不超过 $2^{18}$，所有测试数据的 $q$ 之和不超过 $2\cdot 10^5$。

输出格式

对于每次试验，输出最终栈中位于喝药水奶牛上方的奶牛数量。

样例

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

1
0
0
1
5
0
2
3
1

样例说明

第一组第一次试验中：奶牛 $1$ 和 $2$ 战斗，奶牛 $2$ 获胜，栈变为从下到上 $[1,2]$，技能值为 $3\oplus1=2$；奶牛 $3$ 和 $4$ 战斗，奶牛 $4$ 获胜，栈变为 $[3,4]$，技能值为 $7\oplus5=2$。最终两个栈技能值相同，左侧栈获胜，最终栈为 $[3,4,1,2]$，所以奶牛 $1$ 上方有 $1$ 头奶牛。

数据范围

• $1 \le t \le 10^4$
• $1 \le n \le 18$
• $1 \le q \le 2\cdot 10^5$
• $1 \le a_i,c_i \le 2^{30}$
• $1 \le b_i \le 2^n$
• 所有测试数据的 $2^n$ 之和不超过 $2^{18}$
• 所有测试数据的 $q$ 之和不超过 $2\cdot 10^5$

来源

Codeforces Round 1074 (Div. 4), Problem F - BattleCows