Сяо Q играет с компьютером в пошаговую карточную игру под названием «Абсолютная защита».

У Сяо Q есть колода из $n$ карт, содержащая два типа карт: карты атаки и карты защиты. В начале игры Сяо Q берёт с верха колоды $k \ (1 \le k \le n)$ карт как стартовую руку, затем он сыграет с компьютером несколько раундов сражений.

В начале каждого раунда Сяо Q берёт с верха колоды $2$ карты. Особый случай — если в колоде осталась только $1$ карта, он берёт только 1 карту. Один раунд состоит из двух ходов:

• В первом ходу Сяо Q — атакующий, а компьютер — защитник;
• Во втором ходу Сяо Q — защитник, а компьютер — атакующий.

В каждом ходу атакующий обязан сыграть одну атакующую карту из руки для атаки, защитник обязан сыграть одну защитную карту для защиты. Игрок, который не может сыграть нужную карту, немедленно проигрывает.

У компьютера бесконечное количество карт атаки и защиты, то есть в каждом ходу он всегда может сыграть нужную карту. Чтобы уравнять шансы, Сяо Q может использовать особое умение: когда он является защитником, он может сыграть атакующую карту из руки как защиту. Это умение можно использовать только раз в $3$ раунда, то есть после его использования в одном раунде, оно становится недоступным в следующих двух раундах.

Цель Сяо Q по правилам игры — выжить под яростными атаками компьютера, то есть достичь состояния, при котором колода полностью опустела после окончания какого-либо раунда. В частности, если колода пуста уже в начале игры, Сяо Q немедленно выигрывает. Сяо Q хочет узнать минимальное стартовое число карт $k$, необходимое для достижения цели.

Сяо Q считает эту задачу слишком простой, поэтому он добавил $q$ операций изменения. В $i$-й операции $(1 \le i \le q)$ задаётся положительное число $x_i$, указывающее, что тип $x_i$-й карты (считая от верха к низу колоды) изменяется: атакующая карта превращается в защитную, а защитная — в атакующую. Вам нужно вычислить минимальное значение $k$ до и после каждой операции, чтобы Сяо Q достиг цели.

Формат ввода

Вход читается из стандартного потока ввода.

Эта задача содержит несколько наборов тестов.

Первая строка содержит два неотрицательных целых числа $c, t$, обозначающих номер тестпоинта и количество наборов тестов. $c = 0$ означает, что тестпоинт — это пример.

Затем следуют $t$ наборов тестов. Для каждого набора:

Первая строка содержит два неотрицательных целых числа $n, q$ — размер колоды и количество изменений.

Вторая строка содержит строку длины $n$: $s_1 \dots s_n$, обозначающую колоду от верха к низу. Здесь $s_i = 0$ означает, что $i$-я карта — атакующая, $s_i = 1$ — защитная.

Далее следуют $q$ строк: $i + 2$-я строка $(1 \le i \le q)$ содержит целое число $x_i$ — индекс изменяемой карты (от верха к низу).

Формат вывода

Выводите в стандартный поток вывода.

Для каждого набора тестов выведите строку из $q + 1$ положительных целых чисел $k_0, k_1, \dots, k_q$, где $k_0$ — ответ для начальной колоды, $k_i$ — ответ после $i$-й операции. Эти значения обозначают минимальное стартовое число карт, необходимое для победы.

Пример

Ввод

0 3
5 1
01010
4
7 0
0001000
10 0
0001010000

Вывод

1 1
3
2

Пояснение

В этом примере 3 набора тестов.

Для первого:

• Начальная колода — $01010$. Если взять $k = 1$, возможна следующая стратегия:

  • Рука: ${0}$;
  • Берём 2 карты, играем по одной атакующей и защитной — рука остаётся ${0}$;
  • Ещё 2 карты — снова по одной атакующей и защитной — рука ${0}$, колода пуста.

  Минимальное $k$ — это $1$, значит $k_0 = 1$.

• После изменения колода — $01000$. Аналогично, при $k = 1$ можно выжить, используя специальное умение.

  Значит $k_1 = 1$.

Для второго набора:

При $k = 3$:

• Рука: ${0, 0, 0}$;
• Игра продолжается по правилам и с использованием умения — колода опустеет.

Доказывается, что $k < 3$ не даст возможности победить, значит ответ — $3$.

Для третьего набора:

При $k = 2$:

• Рука: ${0, 0}$;
• В процессе игры с умением можно опустошить колоду.

Доказывается, что $k < 2$ недостаточно. Ответ — $2$.

Пример 2

См. файлы ex_2.in и ex_2.ans в каталоге загрузки — они соответствуют условиям тестпоинта $2$.

Пример 3

См. ex_3.in и ex_3.ans — соответствуют условиям тестпоинтов $5\sim7$.

Пример 4

См. ex_4.in и ex_4.ans — соответствуют условиям тестпоинтов $9, 10$.

Пример 5

См. ex_5.in и ex_5.ans — соответствуют условиям тестпоинта $11$.

Пример 6

См. ex_6.in и ex_6.ans — соответствуют условиям тестпоинтов $12\sim14$.

Ограничения

Пусть $N, Q$ — сумма $n$ и $q$ во всех тестах. Для всех тестов выполнено:

• $1 \le t \le 10^{4}$;
• $1 \le n \le 2 \times 10^{5}$, $N \le 5 \times 10^{5}$;
• $0 \le q \le 2 \times 10^{5}$, $Q \le 5 \times 10^{5}$;
• $s_i \in {0, 1}$;
• $1 \le x_i \le n$.

Особые свойства:

• A: $s_i$ равномерно случайны и независимы;
• B: все $x_i$ различны и $s_{x_i} = 1$;
• C: все $x_i$ различны и $s_{x_i} = 0$;
• D: $x_i$ равномерно случайны и независимы;
• E: $1 \le k_i \le 45$ для всех $0 \le i \le q$.