Strange Addition
Contest: Educational Codeforces Round 91 (Rated for Div. 2)
Difficulty rating: 2600
Tags: data structures, dp, matrices

Let $$$a$$$ and $$$b$$$ be some non-negative integers. Let's define strange addition of $$$a$$$ and $$$b$$$ as following:

1. write down the numbers one under another and align them by their least significant digit;
2. add them up digit by digit and concatenate the respective sums together.

Assume that both numbers have an infinite number of leading zeros.

For example, let's take a look at a strange addition of numbers $$$3248$$$ and $$$908$$$:

You are given a string $$$c$$$, consisting of $$$n$$$ digits from $$$0$$$ to $$$9$$$. You are also given $$$m$$$ updates of form:

- $$$x~d$$$ — replace the digit at the $$$x$$$-th position of $$$c$$$ with a digit $$$d$$$.

Note that string $$$c$$$ might have leading zeros at any point of time.

After each update print the number of pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are non-negative integers and the result of a strange addition of $$$a$$$ and $$$b$$$ is equal to $$$c$$$.

Note that the numbers of pairs can be quite large, so print them modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 5 \cdot 10^5$$$) — the length of the number $$$c$$$ and the number of updates.

The second line contains a string $$$c$$$, consisting of exactly $$$n$$$ digits from $$$0$$$ to $$$9$$$.

Each of the next $$$m$$$ lines contains two integers $$$x$$$ and $$$d$$$ ($$$1 \le x \le n$$$, $$$0 \le d \le 9$$$) — the descriptions of updates.

Output format:
Print $$$m$$$ integers — the $$$i$$$-th value should be equal to the number of pairs $$$(a, b)$$$ such that both $$$a$$$ and $$$b$$$ are non-negative integers and the result of a strange addition of $$$a$$$ and $$$b$$$ is equal to $$$c$$$ after $$$i$$$ updates are applied.

Note that the numbers of pairs can be quite large, so print them modulo $$$998244353$$$.

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
After the first update $$$c$$$ is equal to $$$14$$$. The pairs that sum up to $$$14$$$ are: $$$(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)$$$.

After the second update $$$c$$$ is equal to $$$11$$$.

After the third update $$$c$$$ is equal to $$$01$$$.

Example input:
2 3
14
2 4
2 1
1 0

Example output:
15
12
2

Editorial:
Let's solve the task as if there are no updates. This can be done with a pretty straightforward dp.
$$$dp_i$$$ is the number of pairs $$$(a, b)$$$ such that the result of the strange addition of $$$a$$$ and $$$b$$$ is the prefix of $$$c$$$ of length $$$i$$$. $$$dp_0 = 1$$$. From each state you can add a single digit to $$$a$$$ and to $$$b$$$ at the same time. You can either go to $$$dp_{i+1}$$$ and multiply the answer by the number of pairs of digits than sum up to $$$c_i$$$. Or go to $$$dp_{i+2}$$$ and multiply the answer by the number of pairs of digits than sum up to $$$c_i c_{i+1}$$$. Note that no pair of digits can sum up to a three-digit value, so it makes no sense to go further.
Let's optimize this dp with some data structure. Segment tree will work well. Let the node store the number of ways to split the segment $$$[l; r)$$$ into blocks of size $$$1$$$ or $$$2$$$ so that:
1. both the leftmost character and the rightmost character are not taken into any block;
2. the leftmost character is taken into some block and the rightmost character is not taken into any block;
3. the leftmost character is not taken into any block and the rightmost character is taken into some block;
4. both the leftmost and the rightmost characters are taken into some blocks.
This structure makes the merge pretty manageable. You should glue up the segments in such a way that all the middle characters are taken into some block: either in separate blocks in their own segments or into the same block of length $$$2$$$.
The answer will be in the root of the tree in a value such that both characters are taken.
The update in the segment tree will still work in $$$O(\log n)$$$.
Overall complexity: $$$O(n + m \log n)$$$.