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:
#import<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long LL;
LL i,j,k,m=998244353,n,p=1,q,x,y,a[525000],l[525000],r[525000],z[525000],w[200040];
LL sum(int x,int y,int d)
{
	if(z[d])
	{
		a[d]=z[d]*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=z[d];
			z[(d<<1)+1]=z[d];
		}
		z[d]=0;
	}
	if(x<=l[d]&&r[d]<=y)return a[d];
	if(x>r[d]||y<l[d])return 0;
	return (sum(x,y,d<<1)+sum(x,y,(d<<1)+1))%m;
}
void REP(int x,int y,int d,LL k)
{
	if(z[d])
	{
		a[d]=z[d]*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=z[d];
			z[(d<<1)+1]=z[d];
		}
		z[d]=0;
	}
	if(x<=l[d]&&r[d]<=y)
	{
		a[d]=k*(w[l[d]]-w[r[d]+1]+m)%m;
		if(l[d]<r[d])
		{
			z[d<<1]=k;
			z[(d<<1)+1]=k;
		}
		return;
	}
	if(x>r[d]||y<l[d])return;
	REP(x,y,d<<1,k);
	REP(x,y,(d<<1)+1,k);
	a[d]=a[d<<1]+a[(d<<1)+1];
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(cin>>n>>q;p<=n;)p<<=1;
	for(w[i=n]=1;--i;)w[i]=w[i+1]*10%m;
	for(i=0;i++<n;)
	{
		a[p+i]=w[i];
		l[p+i]=r[p+i]=i;
	}
	for(;i<p;i++)l[p+i]=r[p+i]=i;
	for(i=n;--i;)w[i]=(w[i]+w[i+1])%m;
	for(i=p;--i;)
	{
		a[i]=a[i<<1]+a[(i<<1)+1];
		l[i]=l[i<<1];
		r[i]=r[(i<<1)+1];
	}
	for(;q--;)
	{
		cin>>x>>y>>k;
		REP(x,y,1,k);
		cout<<sum(1,n,1)<<endl;
	}
}