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 <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N=200005;
vector<ll> tree(4*N,0);
vector<int> lazy(4*N,0);
const ll mod=998244353;
vector<ll> pw(N,1);
vector<ll> sum(N,1);

void push(int idx,int l,int r,int m)
{
    if(lazy[idx]!=0)
    {
        tree[2*idx]=(sum[m-l]*lazy[idx])%mod;
        tree[2*idx+1]=(sum[r-(m+1)]*lazy[idx])%mod;
        lazy[2*idx]=lazy[2*idx+1]=lazy[idx];
        lazy[idx]=0;
    }
}

void update(int idx,int l,int r,int ql,int qr,int val)
{
    if(ql>qr) return;
    if(l==ql&&r==qr)
    {
        tree[idx]=(val*sum[r-l])%mod;
        lazy[idx]=val;
    }
    else
    {
        int m=(l+r)/2;
        push(idx,l,r,m);
        update(2*idx,l,m,ql,min(qr,m),val);
        update(2*idx+1,m+1,r,max(ql,m+1),qr,val);
        tree[idx]=(pw[r-(m+1)+1]*tree[2*idx]+tree[2*idx+1])%mod;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,q;
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        pw[i]=(10*pw[i-1])%mod;
        sum[i]=(sum[i-1]+pw[i])%mod;
    }
    update(1,1,n,1,n,1);
    while(q--)
    {
        int l,r,d;
        cin >> l >> r >> d;
        update(1,1,n,l,r,d);
        cout << tree[1] << "\n";
    }
    return 0;
}