CF2268B What a SauSaGe! It's All Meat

在 SauSaGe City，有 $n$ 种不同口味的香肠。Reyhaneh，SauSaGe City 的女王，在皇家仓库中保存了 $a_i$ ( $a_i < 16$ ) 根第 $i$ 种口味的香肠。 随着时间推移，皇家库存会发生 $q$ 次更新。每次更新以 $(p, x)$ 的形式给出，表示将第 $p$ 种口味的香肠数更改为 $x$（即 $a_p := x$）。 Reyhaneh 可以对香肠数量执行如下操作任意多次（可以为 $0$ 次）： - 选择下标 $1 \leq i < n$ 和整数 $1 \leq k \leq 5$，然后将 $a_i$ 和 $a_{i+1}$ 替换为 $a_i \oplus (3 \cdot k)$ 和 $a_{i+1} \oplus (3 \cdot k)$，其中 $\oplus$ 表示[按位异或](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。 在 SauSaGe City，如果某种口味的香肠数量能被 $3$ 整除，则称其为“全肉（All-Meat）”口味。著名的三位香肠评论家——Shafi、Shafaghi 和 Ghaffari——只喜欢“全肉”口味。 在处理任何更新前，以及每次 $q$ 次更新后，你需要回答以下问题：如果 Reyhaneh 可以最优地执行任意多次上述操作，最多能使多少种口味的香肠数量变为评论家们喜欢的“全肉”口味？ 注意：为了每个状态得出答案时所进行的操作仅用于推演，不会影响后续询问所用数组。只有 $q$ 次库存更新（$a_p := x$）是永久生效的。

每个测试点包含多组测试用例。第一行为测试用例个数 $t$（$1 \le t \le 10^4$）。接下来的每个测试用例描述如下。 每个测试用例的第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 2 \cdot 10^5$，$0 \leq q \leq 2 \cdot 10^5$），表示香肠口味数和更新次数。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \leq a_i < 16$），表示每种口味香肠的初始数量。 接下来 $q$ 行，每行包含两个整数 $p$ 和 $x$（$1 \leq p \leq n$，$0 \leq x < 16$），表示将 $a_p$ 赋值为 $x$。 保证所有测试用例中所有 $n$ 之和不超过 $2 \cdot 10^5$。 保证所有测试用例中所有 $q$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出 $q+1$ 个整数。第一个数为初始数组的答案，后面每个数表示每次更新之后的答案。

在第一个测试用例中，初始数组为 $[10, 3]$。选择 $i=1$ 且 $k=1$（即异或 $3$），变为 $[10 \oplus 3, 3 \oplus 3]=[9, 0]$，$9$ 和 $0$ 都能被 $3$ 整除，所以答案是 $2$。完成更新后，数组变为 $[0, 3]$，两项都已能被 $3$ 整除，答案仍然是 $2$。 在第二个测试用例中，初始数组为 $[15, 1, 5]$。选择 $i=2$ 且 $k=3$（异或 $9$），得到 $[15, 1 \oplus 9, 5 \oplus 9]=[15, 8, 12]$，其中 $15$ 和 $12$ 能被 $3$ 整除，答案为 $2$。 第一次更新后，数组为 $[15, 1, 0]$。其中 $15$ 和 $0$ 能被 $3$ 整除，答案为 $2$。 第二次更新后，数组为 $[10, 1, 0]$。选择 $i=1$ 且 $k=3$（异或 $9$），变为 $[10 \oplus 9, 1 \oplus 9, 0]=[3, 8, 0]$，其中 $3$ 和 $0$ 能被 $3$ 整除，答案仍为 $2$。 由 ChatGPT 5 翻译