B. Вот это SauSaGe! Сплошное мясо
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В городе SauSaGe существует $$$n$$$ различных вкусов сосисок. Рейхане, королева города SauSaGe, хранит на королевском складе $$$a_i$$$ ($$$a_i \lt 16$$$) сосисок вкуса $$$i$$$.

Со временем содержимое королевского склада претерпевает $$$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$$$ обозначает побитовое исключающее ИЛИ.

В городе SauSaGe вкус сосисок называют мясным, если их количество делится на $$$3$$$. Три знаменитых критика сосисок — Шафи, Шафаги и Гаффари — любят только мясные вкусы.

До обработки каких-либо изменений, а также после каждого из $$$q$$$ изменений необходимо ответить на следующий вопрос: если Рейхане выполнит произвольное количество операций оптимальным образом, какое максимальное количество вкусов сосисок понравится трём критикам?

Примечание: Операции, выполняемые для поиска ответа для каждого состояния, являются гипотетическими и не влияют на массив для последующих запросов. Однако $$$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 \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$$$.

Выходные данные

Для каждого тестового случая выведите $$$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$$$.