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.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 998244353;
struct Two {
  ll mat[2][2] = {};
  ll &operator()(ll i, ll j) { return mat[i][j]; }
  ll operator()(ll i, ll j) const { return mat[i][j]; }
  Two operator*(const Two &rhs) {
    Two res;
    for (ll i = 0; i < 2; i++) {
      for (ll j = 0; j < 2; j++) {
        for (ll k = 0; k < 2; k++) {
          res.mat[i][j] = (res.mat[i][j] + mat[i][k] * rhs.mat[k][j]) % MOD;
        }
      }
    }
    return res;
  }
};
inline ll f(ll a) { return a + 1; }
inline ll f(ll a, ll b) {
  if (a != 1) {
    return 0;
  }
  return max<ll>(19 - (10 * a + b), 0);
}
const ll N = 5e5;
ll digits[N + 2];
Two seg[4 * N];
void build(ll v, ll vl, ll vr) {
  if (vl == vr) {
    seg[v](0, 0) = f(digits[vl + 1]);
    seg[v](0, 1) = f(digits[vl + 1], digits[vl]);
    seg[v](1, 0) = 1;
    return;
  }
  const ll vm = (vl + vr) >> 1;
  build(2 * v, vl, vm);
  build(2 * v + 1, vm + 1, vr);
  seg[v] = seg[2 * v + 1] * seg[2 * v];
}
void update(ll v, ll vl, ll vr, ll idx) {
  if (vl > vr) {
    return;
  }
  if (vl == idx && vr == idx) {
    seg[v](0, 0) = f(digits[vl + 1]);
    seg[v](0, 1) = f(digits[vl + 1], digits[vl]);
    return;
  }
  const ll vm = (vl + vr) >> 1;
  if (idx <= vm) {
    update(2 * v, vl, vm, idx);
  } else {
    update(2 * v + 1, vm + 1, vr, idx);
  }
  seg[v] = seg[2 * v + 1] * seg[2 * v];
}
int main(int argc, char const *argv[]) {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  ll n, m;
  cin >> n >> m;
  string s;
  cin >> s;
  digits[n + 1] = 0;
  for (ll i = 1; i <= n; i++) {
    digits[i] = s[n - i] - '0';
  }
  build(1, 1, n);
  for (ll i = 1; i <= m; i++) {
    ll x, d;
    cin >> x >> d;
    const ll idx = n + 1 - x;
    digits[idx] = d;
    update(1, 1, n, idx);
    if (idx > 1) {
      update(1, 1, n, idx - 1);
    }
    ll result = (seg[1](1, 0) * f(digits[1]) + seg[1](1, 1)) % MOD;
    cout << result << "\n";
  }
  return 0;
}
