题目描述

在香肠之城，一共有 $n$ 种不同口味的香肠。香肠之城的女王 Reyhaneh 在皇家仓库中存放了 $a_i$（$a_i<16$）根第 $i$ 种口味的香肠。

随着时间推移，仓库会经历 $q$ 次修改操作。每次修改给出 $(p,x)$，含义是将仓库中第 $p$ 种口味香肠的数量改为 $x$（即 $a_p := x$）。

Reyhaneh 可以对香肠进行任意次操作（可以是0次）：

• 选定下标 $1 \le i < n$ 和整数 $1 \le k \le 5$，将 $a_i,a_{i+1}$ 替换为 $a_i \oplus (3\cdot k)$ 与 $a_{i+1} \oplus (3\cdot k)$，其中 $\oplus$ 代表按位异或。

在香肠之城，如果某口味香肠的数量可以被 $3$ 整除，就称它为全肉香肠。三位著名香肠评论家 Shafi、Shafaghi、Ghaffari 只喜欢全肉口味。

在所有修改执行前，以及每一次修改完成之后，你都需要回答：如果 Reyhaneh 以最优方式执行任意次操作，最多能让多少种香肠口味满足三位评论家的喜好？

注意： 为求答案所做的操作只是假想操作，不会改变数组，不影响后续询问。但是 $q$ 次仓库修改（$a_p:=x$）是永久生效的。

输入格式

本题包含多组测试数据。第一行一个整数 $t$（$1 \le t \le 10^4$），代表测试数据组数。接下来是每组测试数据描述。

每组测试数据第一行包含两个整数 $n,q$（$2 \le n \le 2\cdot 10^5$，$0 \le q \le 2\cdot 10^5$），分别代表香肠口味数量与修改次数。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$0 \le a_i <16$），代表初始每种口味香肠数量。

之后 $q$ 行，每行两个整数 $p,x$（$1 \le p \le n$，$0 \le x<16$），表示将 $a_p$ 修改为 $x$。

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

输出格式

对于每组测试数据，输出 $q+1$ 个整数。第一个整数代表初始数组对应的答案，后面 $q$ 个整数依次是每次修改后的答案。

3
2 1
10 3
1 0
3 3
15 1 5
3 0
1 10
2 0
4 0
1 2 3 4

2 2 
2 2 2 3 
1 

说明

第一组测试数据，初始数组是 $[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$。

原题链接

原题链接