H. Бро считает себя избранным
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скибидус думает, что он избранный! Он доказал это, решив эту сложную задачу. Сможете ли вы?

Дана двоичная строка$$$^{\text{∗}}$$$ $$$t$$$, $$$f(t)$$$ определяется как минимальное количество смежных подстрок, каждая из которых состоит из одинаковых символов, на которые можно разбить $$$t$$$. Например, $$$f(\texttt{00110001}) = 4$$$, потому что $$$t$$$ можно разбить как $$$\texttt{[00][11][000][1]}$$$, где каждый сегмент в скобках состоит из одинаковых символов.

Скибидус даёт вам двоичную строку $$$s$$$ и $$$q$$$ запросов. В каждом запросе один символ строки переворачивается (т.е. $$$\texttt{0}$$$ меняется на $$$\texttt{1}$$$, а $$$\texttt{1}$$$ меняется на $$$\texttt{0}$$$), изменения сохраняются после обработки запроса. После каждого запроса выведите сумму по всем $$$f(b)$$$, где $$$b$$$ — это непустая подпоследовательность$$$^{\text{†}}$$$ строки $$$s$$$, по модулю $$$998\,244\,353$$$.

$$$^{\text{∗}}$$$Двоичная строка состоит только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Подпоследовательность строки — это строка, которую можно получить, удалив несколько (возможно, ноль) символов из оригинальной строки.

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

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит двоичную строку $$$s$$$ ($$$1 \leq |s| \leq 2 \cdot 10^5$$$).

Следующая строка каждого набора содержит целое число $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — количество запросов.

Следующая строка содержит $$$q$$$ целых чисел $$$v_1, v_2, \ldots, v_q$$$ ($$$1 \leq v_i \leq |s|$$$), обозначающих, что $$$s_{v_i}$$$ переворачивается в $$$i$$$-м запросе.

Гарантируется, что сумма $$$|s|$$$ и сумма $$$q$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите $$$q$$$ целых чисел в одной строке — ответ после каждого запроса по модулю $$$998\,244\,353$$$.

Пример
Входные данные
3
101
2
1 3
10110
3
1 2 3
101110101
5
7 2 4 4 1
Выходные данные
10 7 
61 59 67 
1495 1169 1417 1169 1396
Примечание

В первом тестовом случае $$$s$$$ становится $$$\texttt{001}$$$ после первого запроса. Давайте посчитаем ответ для каждой подпоследовательности:

  • $$$f(s_1) = f(\texttt{0}) = 1$$$
  • $$$f(s_2) = f(\texttt{0}) = 1$$$
  • $$$f(s_3) = f(\texttt{1}) = 1$$$
  • $$$f(s_1 s_2) = f(\texttt{00}) = 1$$$
  • $$$f(s_1 s_3) = f(\texttt{01}) = 2$$$
  • $$$f(s_2 s_3) = f(\texttt{01}) = 2$$$
  • $$$f(s_1 s_2 s_3) = f(\texttt{001}) = 2$$$

Сумма этих значений равна $$$10$$$, по модулю $$$998\,244\,353$$$.