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<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=2e5+10,XJQ=998244353;
ll n,q,s[N];
ll lazy[N*4],t[N*4];
void Downdata(ll x,ll l,ll m,ll r){
	if(!lazy[x])return;
	ll val=lazy[x];
	lazy[x*2]=lazy[x*2+1]=lazy[x];
	t[x*2]=(s[m]-s[l-1]+XJQ)%XJQ*val%XJQ;
	t[x*2+1]=(s[r]-s[m]+XJQ)%XJQ*val%XJQ;
	lazy[x]=0;return;
}
void Change(ll x,ll L,ll R,ll l,ll r,ll val){
	if(L==l&&R==r){
		lazy[x]=val;
		t[x]=(s[R]-s[L-1]+XJQ)%XJQ*val%XJQ;
		return;
	}
	ll mid=(L+R)>>1;
	Downdata(x,L,mid,R);
	if(r<=mid)Change(x*2,L,mid,l,r,val);
	else if(l>mid)Change(x*2+1,mid+1,R,l,r,val);
	else Change(x*2,L,mid,l,mid,val),Change(x*2+1,mid+1,R,mid+1,r,val);
	t[x]=(t[x*2]+t[x*2+1])%XJQ;
}
int main()
{
	scanf("%lld%lld",&n,&q);
	s[1]=1;
	for(ll i=2;i<=n;i++)
		s[i]=s[i-1]*10%XJQ;
	for(ll i=1;i<=n;i++){
		s[i]=(s[i]+s[i-1])%XJQ;
		Change(1,1,n,i,i,1);
	}
	while(q--){
		ll l,r,d;
		scanf("%lld%lld%lld",&l,&r,&d);
		l=n-l+1;r=n-r+1;swap(l,r);
		Change(1,1,n,l,r,d);
		   printf("%lld\n",t[1]);
	}
	return 0;
}