1380_F. Strange Addition
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:

<image>

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

The first line contains two integers n and m (1 ≤ n, m ≤ 5 ⋅ 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 ≤ x ≤ n, 0 ≤ d ≤ 9) — the descriptions of updates.

Output

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.

Example

Input


2 3
14
2 4
2 1
1 0


Output


15
12
2

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.
```python
from sys import stdin
import sys

class LazySegTree:

    def __init__(self,N,first):
        
        self.LV = (N-1).bit_length() 
        self.NO = 2**self.LV
        self.First = first
        self.data = [first] * (2*self.NO)
        self.lazy = [None] * (2*self.NO)

    def calc(self,l,r):
        return min(l,r)

    def gindex(self,l,r):

        L = l + self.NO
        R = r + self.NO

        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1

        while L:
            yield L
            L >>= 1

    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None

    def update(self , l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
     
        L = self.NO + l; R = self.NO + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1

        
        for i in ids:
            self.data[i-1] = self.calc(self.data[2*i-1], self.data[2*i])

    def query(self , l, r):
        
        self.propagates(*self.gindex(l, r))
        L = self.NO + l; R = self.NO + r

        s = self.First
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(s, self.data[R-1])
            if L & 1:
                s = self.calc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def inverse(a,mod):
    return pow(a,mod-2,mod)

def calc(tmpR):
    ret = dp[tmpR-Lside[tmpR]] * dnum[c[tmpR]]
    if tmpR - Lside[tmpR] > 0:
        ret += dp[tmpR-Lside[tmpR]-1] * dnum[c[tmpR] + 10]
    return ret

mod = 998244353
n,m = map(int,stdin.readline().split())

c = list(stdin.readline()[:-1])
c = list(map(int,c))
c = [0] + c + [9]

#divide
dnum = [0] * 20
for i in range(10):
    for j in range(10):
        dnum[i+j] += 1

#dp
dp = [0] * (n+10)
dp[0] = 1
for i in range(n+8):
    dp[i+1] += dp[i] * 2
    dp[i+1] %= mod
    dp[i+2] += dp[i] * 8
    dp[i+2] %= mod

#construct

ST = LazySegTree(len(c),float("inf"))
Lside = [None] * len(c)

tmpR = None
ans = 1
for i in range(len(c)-1,-1,-1):

    if c[i] != 1:
        if tmpR != None:
            ST.update(i+1,tmpR+1,tmpR)
            Lside[tmpR] = i+1
            
            #now = dp[tmpR-i-1] * dnum[c[tmpR]]
            #if tmpR-i-1 > 0:
            #    now += dp[tmpR-i-2] * dnum[c[tmpR] + 10]
            ans *= calc(tmpR)
            ans %= mod
        tmpR = i

print (ans * inverse(dnum[9] , mod) % mod , file=sys.stderr)
anss = []
vvv = inverse(dnum[9] , mod)

for loop in range(m):

    x,d = map(int,stdin.readline().split())

    if d == 1:
        if c[x] != 1:

            now = 1
            newR = ST.query(x+1,x+2)
            now *= inverse(calc(x) * calc(newR),mod)
            ST.update(Lside[x],x+1,newR)
            c[x] = d
            Lside[newR] = Lside[x]
            now *= calc(newR)
            ans *= now

    else:
        if c[x] != 1:
            now = 1
            now *= inverse(calc(x) , mod)
            c[x] = d
            now *= calc(x)
            ans *= now
        else:
            now = 1
            oldR = ST.query(x,x+1)
            now *= inverse(calc(oldR) , mod)
            c[x] = d
            Lside[x] = Lside[oldR]
            Lside[oldR] = x+1
            ST.update(Lside[x],x+1,x)
            now *= calc(oldR) * calc(x)
            ans *= now
            
    ans %= mod
    #print (ans * inverse(dnum[9] , mod) % mod )   
    anss.append(ans * vvv % mod)

print ("\n".join(map(str,anss)))
    
```