Скибидус думает, что он избранный! Он доказал это, решив эту сложную задачу. Сможете ли вы?
Дана двоичная строка\(^{\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\).
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел в одной строке — ответ после каждого запроса по модулю \(998\,244\,353\).
Примечание
В первом тестовом случае \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|