Busy Beaver 有一个包含 $N$ 个整数的数组 $a_1, a_2, \dots, a_N$，其中 $1 \le a_i < 2^K$。作为一个程序员，他喜欢用二进制写数字！

定义一个正整数数组的“圆度”（roundness）为该数组所有元素二进制表示中末尾 $0$ 的总个数。例如，数组 $[2, 3, 6, 8, 10]$ 的二进制表示为 $[10, 11, 110, 1000, 1010]$，因此其圆度为 $1 + 0 + 1 + 3 + 1 = 6$。

Busy Beaver 可以选择一个整数 $x$，满足 $0 \le x < 2^K$ 且对于所有 $i$ 都有 $x \neq a_i$，然后将数组中的每个元素替换为 $a_i \oplus x$，其中 $\oplus$ 表示按位异或。对于当前的数组，求此操作后可能达到的最大圆度。

接着会有 $Q$ 次更新。每次查询更新 $a_i \leftarrow v$，其中 $1 \le i \le N$ 且 $1 \le v < 2^K$。注意，更新是持久的，这意味着每次更新都会修改数组，后续的更新应在当前状态的基础上进行。

输出初始数组的最大圆度，以及每次更新后的最大圆度。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$) —— 测试用例的数量。

每个测试用例的第一行包含三个空格分隔的整数 $N, Q, K$ ($1 \le N \le 2 \cdot 10^5, 0 \le Q \le 2 \cdot 10^5, 1 \le K \le 60$)。

每个测试用例的第二行包含 $N$ 个空格分隔的整数 $a_1, \dots, a_N$ ($1 \le a_i < 2^K$) —— 数组 $a$ 的成员。

接下来的 $Q$ 行，每行包含两个整数 $i$ 和 $v$ ($1 \le i \le N, 1 \le v < 2^K$)，描述一次更新。

所有测试用例的 $N$ 之和不超过 $2 \cdot 10^5$。 所有测试用例的 $Q$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $Q + 1$ 行。

第一行应包含一个整数 —— 更新前的答案。 接下来的 $Q$ 行中，第 $i$ 行应包含第 $i$ 次更新后的答案。

子任务

本题共有三个子任务。令 $\sum N$ 表示所有测试用例中 $N$ 的总和，令 $\sum Q$ 表示所有测试用例中 $Q$ 的总和。

• (20 分)：$\sum N, \sum Q \le 1000, K \le 25$。此外，保证 $K > 1$，且对于所有 $i$ 有 $a_i < 2^{K-1}$，所有更新中 $v < 2^{K-1}$。
• (30 分)：$\sum N, \sum Q \le 1000, K \le 25$。
• (50 分)：无附加限制。

样例

输入 1

2
5 0 3
1 1 2 3 4
4 4 3
1 3 5 7
2 4
1 4
3 4
4 4

输出 1

5
0
4
4
6
8

说明

对于第一个测试用例，最优的 $x$ 值为 $x = 5$，得到 $a \oplus 5 = [4, 4, 7, 6, 1]$。圆度为 $5$。

对于第二个测试用例，在第一次更新前，由于 $x \neq a_i$ 对所有 $i$ 成立，$x$ 必须为偶数，这意味着所有的 $a \oplus x$ 均为奇数，因此答案为 $0$。第一次更新后，数组变为 $a = [1, 4, 5, 7]$。此时，$x = 3$ 提供了最优结果，得到 $a \oplus 3 = [2, 7, 6, 4]$，圆度为 $4$。