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;
const int maxn=2e5+10;
const long long mod=998244353L;
long long t[maxn<<2],laz[maxn<<2],n,q,sum[maxn];
long long qpow(long long base,long long k){
	long long res=1;
	while(k){
		if(k&1){
			res=res*base%mod;
		}
		k/=2;
		base=base*base%mod;
	}
	return res%mod;
}
void make(int l,int r,int num){
	if(l==r){
		t[num]=qpow(10,n-l);
		laz[num]=0;
		return;
	}
	else{
		int mid=(l+r)>>1;
		make(l,mid,num<<1);
		make(mid+1,r,num<<1|1);
		t[num]=(t[num<<1]+t[num<<1|1])%mod;
	}
}
void update(int x,int y,int nv,int l,int r,int num){
	int mid=(l+r)/2;
	if(x<=l&&y>=r){
		laz[num]=nv;
		t[num]=(sum[n-l]-sum[n-r-1]+10*mod)%mod*nv%mod;
		return;
	}
	if(laz[num]){
		laz[num<<1]=laz[num<<1|1]=laz[num];
		t[num*2]=laz[num]*(sum[n-l]-sum[n-mid-1]+10*mod)%mod;
		t[num*2+1]=laz[num]*(sum[n-mid-1]-sum[n-r-1]+10*mod)%mod;
		laz[num]=0;
	}
	if(y<=mid) update(x,y,nv,l,mid,num*2);   /*注意找儿子的时候不能改动区间*/ 
	else if(x>mid) update(x,y,nv,mid+1,r,num*2+1);
	else{
		update(x,y,nv,l,mid,num*2);
		update(x,y,nv,mid+1,r,num*2+1);
	}
	t[num]=(t[num<<1]+t[num<<1|1])%mod;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	long long x=1;
	sum[0]=1;
	for(int i=1;i<=n;i++){
		x=x*10%mod;
		sum[i]=(sum[i-1]+x)%mod;
	}
	make(1,n,1);
	for(int i=1,x,y,w;i<=q;i++){
		cin>>x>>y>>w;
		update(x,y,w,1,n,1);
		cout<<t[1]<<endl;
	}
}