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;
typedef long long ll;
const int mod=998244353;
const int N=200010;
ll lazy[N<<2],tr[N<<2];
ll s[N];
ll sum[N];
void pushup(int l,int mid,int r,int u){
    tr[u]=(tr[u<<1|1]+1ll*s[r-mid]*tr[u<<1]%mod)%mod;
}
void init(int l,int r,int u){
    if(l==r){
        tr[u]=1;
        return ;
    }
    int mid=l+r>>1;
    init(l,mid,u<<1);
    init(mid+1,r,u<<1|1);
    pushup(l,mid,r,u);
}
void pushdown(int l,int r,int u){
    int mid=l+r>>1;
    if(lazy[u]){
        tr[u<<1]=(1ll*sum[mid-l]*lazy[u])%mod;
        tr[u<<1|1]=(1ll*sum[r-mid-1]*lazy[u])%mod;
        lazy[u<<1]=lazy[u<<1|1]=lazy[u];
        lazy[u]=0;
    }
}
void update(int l,int r,int a,int b,int d,int u){
    if(l<=a&&b<=r){
        lazy[u]=d;
        tr[u]=(sum[b-a]*d)%mod;
//        cout<<a<<' '<<b<<' '<<tr[u]<<endl;
        return ;
    }
    pushdown(a,b,u);
    int mid=a+b>>1;
    if(l<=mid)update(l,r,a,mid,d,u<<1);
    if(r>mid) update(l,r,mid+1,b,d,u<<1|1);
    pushup(a,mid,b,u);
}
int main()
{
    s[0]=sum[0]=1;
    int n,q;
    cin>>n>>q;

    for(int i=1;i<=n;++i)s[i]=1ll*s[i-1]*10%mod;
    for(int i=1;i<=n;++i)sum[i]=(sum[i-1]+s[i])%mod;
    init(1,n,1);
    for(int i=1;i<=q;++i){
        int l,r,d;
        cin>>l>>r>>d;
//        cout<<l<<' '<<r<<endl;
        update(l,r,1,n,d,1);
//		cout<<query(1,4,1,n,1)<<endl; 
        cout<<tr[1]<<endl;
    }
}