Пусть \(a\) и \(b\) будут некоторыми неотрицательными целыми числами. Определим странное сложение \(a\) и \(b\) следующим образом:
- запишем числа одно под другим и выровняем их по младшему разряду;
- сложим числа поразрядно и запишем полученные суммы одну за другой.
Будем считать, что у обоих чисел бесконечное число лидирующих нулей.
Например, взглянем на странное сложение чисел \(3248\) и \(908\):
Вам задана строка \(c\), состоящая из \(n\) цифр от \(0\) до \(9\). Также заданы \(m\) запросов обновления следующего вида:
- \(x~d\) — заменить цифру на \(x\)-й позиции \(c\) на цифру \(d\).
Обратите внимание, что \(c\) может иметь лидирующие нули в любой момент времени.
После каждого обновления выведите количество пар чисел \((a, b)\) таких, что \(a\) и \(b\) оба являются неотрицательными целыми числами и результат странного сложения \(a\) и \(b\) равен \(c\).
Обратите внимание, что количество пар может быть довольно велико, поэтому требуется вывести его по модулю \(998244353\).
Выходные данные
Выведите \(m\) целых чисел — \(i\)-е значение должно быть равно количеству пар чисел \((a, b)\) таких, что \(a\) и \(b\) оба являются неотрицательными целыми числами и результат странного сложения \(a\) и \(b\) равен \(c\) после применения \(i\) запросов обновления.
Обратите внимание, что количество пар может быть довольно велико, поэтому требуется вывести его по модулю \(998244353\).
Примечание
После первого запроса \(c\) равно \(14\). Пары, которые складываются в \(14\): \((0, 14)\), \((1, 13)\), \((2, 12)\), \((3, 11)\), \((4, 10)\), \((5, 9)\), \((6, 8)\), \((7, 7)\), \((8, 6)\), \((9, 5)\), \((10, 4)\), \((11, 3)\), \((12, 2)\), \((13, 1)\), \((14, 0)\).
После второго запроса \(c\) равно \(11\).
После третьего запроса \(c\) равно \(01\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 3
14
2 4
2 1
1 0
|
15
12
2
|