A. Delete, Deduct, and Destroy
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice is playing with a function $$$f(x, k)$$$. Here, $$$x$$$ is a positive integer with at least two digits and no leading zeros, and $$$k$$$ is an integer satisfying $$$1 \le k \le$$$ (number of digits of $$$x$$$). To evaluate $$$f(x, k)$$$, Alice deletes the $$$k$$$-th digit of $$$x$$$ from the right and obtains an integer $$$y$$$ ($$$y$$$ may contain leading zeros). Then we define $$$f(x, k) = x - y$$$. For example $$$f(1234, 2) = 1234 - 124 = 1110$$$ because deleting the 2nd digit from the right of 1234 results in 124.

Alice wants to know how many ways she can choose $$$x$$$ and $$$k$$$ such that $$$f(x, k) = y$$$, for a given integer $$$y$$$. For any integer $$$z$$$, define $$$g(z)$$$ as the number of pairs $$$(x, k)$$$ satisfying $$$f(x, k) = z$$$.

For example, $$$g(10) = 11$$$ because there are 11 valid pairs $$$(x, k)$$$ such that $$$f(x, k) = 10$$$:

  • For $$$k = 1$$$, the only valid pair is $$$(11, 1)$$$.
  • For $$$k = 2$$$, the pairs are $$$(10, 2), (11, 2), (12, 2), \ldots, (19, 2)$$$.

You are given a number $$$a_0$$$ with $$$n$$$ digits (may include leading zeros). You need to answer $$$q$$$ queries. In the $$$i$$$-th query, you will be given a position $$$p_i$$$ and a digit $$$d_i$$$. You can find $$$a_i$$$ by updating the $$$p_i$$$-th digit of $$$a_{i - 1}$$$ (from the right) to $$$d_i$$$. You need to output the value of $$$g(a_i)$$$ modulo $$$998{,}244{,}353$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the number of digits in the initial number $$$a_0$$$.

The second line of the input contains a string of $$$n$$$ digits (each digit is between '0' and '9', inclusive) — the initial number $$$a_0$$$.

The third line contains a single integer $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — the number of queries.

Each of the next $$$q$$$ lines contains two space-separated integers $$$p_i$$$ and $$$d_i$$$ ($$$1 \leq p_i \leq n$$$, $$$0 \leq d_i \leq 9$$$) — the position (from the right) and the new digit for the $$$i$$$-th query.

Output

For each query, output one integer in a line — the value of $$$g(a_i) \mod 998{,}244{,}353$$$ in a new line.

Example
Input
3
010
4
2 1
2 0
1 7
3 2
Output
11
0
0
2
Note

In the sample test case, $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, and $$$a_4$$$ are $$$010$$$, $$$000$$$, $$$007$$$, and $$$207$$$, respectively.

As explained in the statement, $$$g(10) = 11$$$. $$$g(0) = 0$$$ because there is no valid pair $$$(x, k)$$$ that produces $$$f(x, k) = 0$$$. $$$g(7) = 0$$$ because there is no valid pair $$$(x, k)$$$ that produces $$$f(x, k) = 7$$$. Note that $$$(7, 1)$$$ is not valid since $$$x$$$ must have at least two digits. It can be shown that $$$g(207) = 2$$$.