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;

inline ll read(){
    char ch=getchar();ll x=0,f=1;
    while(ch<'0' || ch>'9') {
       if(ch=='-') f=-1;
      	  ch=getchar();
    }
    while(ch<='9' && ch>='0') {
       x=x*10+ch-'0';
       ch=getchar();
    }
    return x*f;
}

const int M=998244353; 

struct node{
	int l,r;
	int add;
	ll sum;
	ll base;
}t[4040404];

ll res=1;

void build(int p,int l,int r){
	t[p].l=l;t[p].r=r;
	if(l==r){
		t[p].base=res;
		t[p].sum=t[p].base;
		res=(res*10)%M;
		return ;
	}
	int mid=l+r>>1;
	build(p*2+1,mid+1,r);
	build(p*2,l,mid);
	t[p].base=(t[p*2].base+t[p*2+1].base)%M;
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%M;
}

void update(int p){
	if(t[p].add){
		t[p*2].add=t[p].add;
		t[p*2+1].add=t[p].add;
		t[p*2].sum=(t[p*2].base*t[p].add)%M;
		t[p*2+1].sum=(t[p*2+1].base*t[p].add)%M;
		t[p].add=0;
	}
}

void change(int p,int l,int r,int x){
	if(l<=t[p].l && r>=t[p].r){
		t[p].sum=(t[p].base*x)%M;
		t[p].add=x;
		return ;
	}
	update(p);
	int mid=t[p].l+t[p].r>>1;
	if(l<=mid) change(p*2,l,r,x);
	if(r>mid) change(p*2+1,l,r,x);
	t[p].sum=(t[p*2].sum+t[p*2+1].sum)%M;
}

int main(){
	int n=read(),m=read();
	ll res=0;
	build(1,1,n);
	for(int i=1;i<=m;i++){
		int l=read(),r=read(),x=read();
		change(1,l,r,x);
		printf("%lld\n",t[1].sum);
	}
	return 0;
}