H. Построй из суффиксов
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано целое число $$$n$$$ и последовательность $$$a$$$ из $$$n-1$$$ целых чисел: каждый элемент равен либо $$$0$$$, либо $$$1$$$.

Требуется построить такую строку длины $$$n$$$, что:

  • каждая буква — одна из «abcd»;
  • если $$$a_i=1$$$, то $$$i$$$-й суффикс строки лексикографически меньше $$$(i+1)$$$-го суффикса;
  • если $$$a_i=0$$$, то $$$i$$$-й суффикс строки лексикографически больше $$$(i+1)$$$-го суффикса.

Будут заданы $$$q$$$ запросов вида:

  • $$$i$$$ ($$$1 \le i \le n - 1$$$) — сменить значение $$$a_i$$$ на противоположное (если $$$a_i=0$$$, то установить $$$a_i$$$ в $$$1$$$, и наоборот).

После каждого запроса выведите количество различных строк, удовлетворяющих данным ограничениям, по модулю $$$998\,244\,353$$$.

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

В первой строке записаны два целых числа $$$n$$$ и $$$q$$$ ($$$2 \le n \le 10^5$$$; $$$1 \le q \le 10^5$$$) — длина строки и количество запросов.

Во второй строке записаны $$$n-1$$$ целых чисел $$$a_1, a_2, \dots, a_{n-1}$$$ ($$$a_i \in \{0, 1\}$$$) — ограничения на суффиксы строки.

В каждой из следующих $$$q$$$ строк задан запрос: одно целое число $$$i$$$ ($$$1 \le i \le n - 1$$$) — сменить значение $$$a_i$$$ на противоположное (если $$$a_i=0$$$, то установить $$$a_i$$$ в $$$1$$$, и наоборот).

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

После каждого запроса выведите количество различных строк, удовлетворяющих данным ограничениям, по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
2 2
0
1
1
Выходные данные
6
10
Входные данные
3 4
0 0
1
2
1
2
Выходные данные
20
10
14
20
Входные данные
10 10
0 0 0 1 1 1 0 1 0
4
1
8
4
2
9
5
6
6
8
Выходные данные
1815
3201
2710
2776
2290
1644
2668
1271
2668
2436
Примечание

$$$i$$$-й суффикс строки — это последовательная подстрока, которая начинается в $$$i$$$-й позиции и заканчивается в последней позиции.

Строка $$$a$$$ лексикографически меньше строки $$$b$$$, если и только если выполняется один из следующих пунктов:

  • $$$a$$$ — префикс $$$b$$$, но $$$a \ne b$$$;
  • в первой позиции, где $$$a$$$ и $$$b$$$ различны, в строке $$$a$$$ находится буква, которая встречается в алфавите раньше, чем соответствующая буква в $$$b$$$.

Две строки $$$a$$$ и $$$b$$$ длины $$$n$$$ различаются, если существует такая позиция $$$i$$$, что $$$a_i \neq b_i$$$