F. MEX-ИЛИ-мания
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

Последовательность чисел $$$b_1, b_2, \ldots, b_n$$$ является хорошей, если $$$\operatorname{mex}(b_1, b_2, \ldots, b_n) - (b_1 | b_2 | \ldots | b_n) = 1$$$. Здесь $$$\operatorname{mex(c)}$$$ обозначает MEX$$$^{\text{∗}}$$$ набора чисел $$$c$$$, а $$$|$$$ обозначает операцию побитового ИЛИ.

У Шохага есть целочисленная последовательность $$$a_1, a_2, \ldots, a_n$$$. Он выполнит следующие $$$q$$$ обновлений последовательности $$$a$$$:

  • $$$i$$$ $$$x$$$ — увеличить $$$a_i$$$ на $$$x$$$.

После каждого обновления помогите Шохагу найти длину самого длинного хорошего подмассива$$$^{\text{†}}$$$ массива $$$a$$$.

$$$^{\text{∗}}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$y$$$, которое не встречается в наборе чисел $$$c$$$.

$$$^{\text{†}}$$$Массив $$$d$$$ является подмассивом массива $$$f$$$, если $$$d$$$ может быть получен из $$$f$$$ удалением нескольких (возможно, ни одного или всех) элементов с начала и нескольких (возможно, ни одного или всех) элементов с конца.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le n$$$).

Следующие $$$q$$$ строк каждого набора входных данных имеют следующий вид:

  • $$$i$$$ $$$x$$$ ($$$1 \le i, x \le n$$$) — это означает, что вы должны увеличить $$$a_i$$$ на $$$x$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$ и сумма $$$q$$$ не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ строк — в $$$i$$$-й строке выведите длину самого длинного хорошего подмассива $$$a$$$ после $$$i$$$-го обновления.

Пример
Входные данные
2
6 3
0 0 1 0 1 0
6 1
3 2
6 3
3 1
1 3 1
1 1
Выходные данные
6
3
2
0
Примечание

В первом наборе входных данных после первого обновления массив становится $$$[0, 0, 1, 0, 1, 1]$$$. Весь массив является хорошим, так как $$$\operatorname{mex}([0, 0, 1, 0, 1, 1]) - (0 | 0 | 1 | 0 | 1 | 1) = 2 - 1 = 1$$$.

После второго обновления массив становится равен $$$[0, 0, 3, 0, 1, 1]$$$, и его подмассив $$$[0, 1, 1]$$$ имеет максимальную длину среди всех хороших подмассивов.

Наконец, после третьего обновления массив становится равен $$$[0, 0, 3, 0, 1, 4]$$$, и два его подмассива $$$[0, 0]$$$ и $$$[0, 1]$$$ имеют максимальную длину среди всех хороших подмассивов.