Problem: You have a string S of length N. Initially, all characters in S are `1`s.

You will perform queries Q times. In the i-th query, you are given two integers L_i, R_i and a character D_i (which is a digit). Then, you must replace all characters from the L_i-th to the R_i-th (inclusive) with D_i.

After each query, read the string S as a decimal integer, and print its value modulo 998,244,353.

Constraints

* 1 \leq N, Q \leq 200,000
* 1 \leq L_i \leq R_i \leq N
* 1 \leq D_i \leq 9
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N Q
L_1 R_1 D_1
:
L_Q R_Q D_Q


Output

Print Q lines. In the i-th line print the value of S after the i-th query, modulo 998,244,353.

Examples

Input

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1


Output

11222211
77772211
77333333
72333333
72311333


Input

200000 1
123 456 7


Output

641437905

Solution (in CPP):

Solution:
#include <iostream>

using namespace std;

#define int long long

const int N = 2e5 + 10, mod = 998244353;

int n, q, ten[N], seg[N << 2], lazy[N << 2];

int t(int l, int r) {
  return ((ten[n - l + 1] - ten[n - r]) % mod + mod) % mod;
}

void push(int n, int i, int j) {
  if (lazy[n]) {
    if (i != j) {
      lazy[n << 1] = lazy[n << 1 | 1] = lazy[n];
    }
    seg[n] = (lazy[n] * t(i, j)) % mod;
    lazy[n] = 0;
  }
}

void update(int i, int j, int l, int r, int v, int n) {
  push(n, i, j);
  if (i > r || j < l) {
    return;
  }
  if (i >= l && j <= r) {
    lazy[n] = v;
    push(n, i, j);
    return;
  }
  int m = (i + j) >> 1;
  update(i, m, l, r, v, n << 1);
  update(m + 1, j, l, r, v, n << 1 | 1);
  seg[n] = (seg[n << 1] + seg[n << 1 | 1]) % mod;
}

int32_t main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);    
  cin >> n >> q;
  ten[1] = 1;
  for (int i = 2; i <= n; ++i) {
    ten[i] = (ten[i - 1] * 10) % mod;
  }
  for (int i = 2; i <= n; ++i) {
    ten[i] = (ten[i - 1] + ten[i]) % mod;
  }
  update(1, n, 1, n, 1, 1);
  while (q--) {
    int l, r, d;
    cin >> l >> r >> d;
    update(1, n, l, r, d, 1);
    cout << seg[1] << '\n';
  }
  return 0;
}