CF2268B.What a SauSaGe! It's All Meat

In SauSaGe City, there are $n$ different flavors of sausages. Reyhaneh, the Queen of SauSaGe City, keeps $a_i$ ($a_i \lt 16$) sausages of flavor $i$ in the royal warehouse.

Over time, the royal inventory undergoes $q$ updates. Each update is given in the form $(p, x)$, which means the number of sausages of flavor $p$ in the warehouse is changed to $x$ (i.e., $a_p := x$).

Reyhaneh can perform the following operation on the sausages any number of times (possibly zero):

• Choose an index $1 \leq i \lt n$ and an integer $1 \leq k \leq 5$, then replace $a_i$ and $a_{i+1}$ with $a_i \oplus (3 \cdot k)$ and $a_{i+1} \oplus (3 \cdot k)$, respectively, where $\oplus$ denotes the bitwise XOR.

In SauSaGe City, a sausage flavor is called All-Meat if its quantity is divisible by $3$. Three famous sausage critics — Shafi, Shafaghi, and Ghaffari — only like flavors that are All-Meat.

Before processing any updates, and after each of the $q$ updates, you need to answer the following question: If Reyhaneh performs an arbitrary number of operations optimally, what is the maximum possible number of sausage flavors that the three critics would like?

Note: The operations you perform to find the answer for each state are hypothetical and do not affect the array for subsequent queries. However, the $q$ inventory updates ($a_p := x$) are permanent.

在萨萨格（SauSaGe）城中，共有 $n$ 种不同风味的香肠。萨萨格城的女王蕾亚内赫（Reyhaneh）在皇家仓库中储存了第 $i$ 种风味的香肠 $a_i$ 根（其中 $a_i \lt 16$）。

随着时间推移，皇家库存将经历 $q$ 次更新。每次更新以 $(p, x)$ 的形式给出，表示将仓库中第 $p$ 种风味香肠的数量修改为 $x$（即 $a_p := x$）。

蕾亚内赫可以对香肠执行以下操作任意多次（包括零次）：

• 选择一个下标 $1 \leq i \lt 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$ 表示按位异或运算。

在萨萨格城中，若某种香肠风味的数量能被 $3$ 整除，则该风味被称为“全肉型”（All-Meat）。三位著名的香肠评论家——沙菲（Shafi）、沙法吉（Shafaghi）和加法里（Ghaffari）——只喜欢“全肉型”风味。

在处理任何更新之前，以及每次 $q$ 次更新之后，你都需要回答如下问题：若蕾亚内赫以最优方式执行任意次数的操作，三位评论家会喜欢的香肠风味种类数的最大可能值是多少？

注意：为回答每个状态而执行的操作仅为假设性操作，不会影响后续查询所用的数组。但 $q$ 次库存更新（即 $a_p := x$）是永久生效的。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $q$ ($2 \leq n \leq 2 \cdot 10^5$, $0 \leq q \leq 2 \cdot 10^5$) — the number of sausage flavors and the number of updates, respectively.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \leq a_i \lt 16$) — the initial numbers of sausages of each flavor.

Then $q$ lines follow, each containing two integers $p$ and $x$ ($1 \leq p \leq n$, $0 \leq x \lt 16$), meaning that $a_p$ is replaced with $x$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

It is guaranteed that the sum of $q$ over all test cases does not exceed $2\cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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 \lt 16$）—— 表示每种口味初始的香肠数量。

接下来是 $q$ 行，每行包含两个整数 $p$ 和 $x$（$1 \leq p \leq n$，$0 \leq x \lt 16$），表示将 $a_p$ 替换为 $x$。

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

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

For each test case, output $q + 1$ integers. The first integer denotes the answer for the initial array. The next $q$ integers denote the answer for each update.

对于每个测试用例，输出 $q + 1$ 个整数。第一个整数表示初始数组的答案；接下来的 $q$ 个整数分别表示每次更新后的答案。

In the first test case, the initial array is $[10, 3]$. By choosing $i = 1$ and $k = 1$ (so we apply XOR with $3$), we obtain $[10 \oplus 3, 3 \oplus 3] = [9, 0]$, and both $9$ and $0$ are divisible by $3$. After the update, the array becomes $[0, 3]$, where both elements are already divisible by $3$, so the answer is $2$ in both states.

In the second test case, the initial array is $[15, 1, 5]$. By choosing $i = 2$ and $k = 3$ (XOR with $9$), we get $[15, 1 \oplus 9, 5 \oplus 9] = [15, 8, 12]$, and $15$ and $12$ are divisible by $3$, so the answer is $2$.

After the first update, the array is $[15, 1, 0]$. Again, two elements ($15$ and $0$) are divisible by $3$, so the answer is $2$.

After the second update, the array is $[10, 1, 0]$. Choosing $i = 1$ and $k = 3$ (XOR with $9$) gives $[10 \oplus 9, 1 \oplus 9, 0] = [3, 8, 0]$, where $3$ and $0$ are divisible by $3$, so the answer remains $2$.

在第一个测试用例中，初始数组为 $[10, 3]$。选择 $i = 1$ 和 $k = 1$（即对元素执行与 $3$ 的异或操作），得到 $[10 \oplus 3, 3 \oplus 3] = [9, 0]$，其中 $9$ 和 $0$ 均能被 $3$ 整除。更新后，数组变为 $[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$。