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](https://en.wikipedia.org/wiki/Bitwise_operation#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.

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 $ .

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.

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 $ .