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;

const ll N=200010,MOD=998244353;
ll n,Q;
ll mod[11][N],power[N];

struct Segtree
{
	ll l[N*4],r[N*4],lazy[N*4];
	ll sum[N*4];
	
	void build(ll x,ll ql,ll qr)
	{
		l[x]=ql; r[x]=qr;
		if (ql==qr)
		{
			sum[x]=1;
			return;
		}
		ll mid=(ql+qr)>>1;
		build(x*2,ql,mid); build(x*2+1,mid+1,qr);
		sum[x]=(sum[x*2]*power[r[x*2+1]-l[x*2+1]+1]%MOD+sum[x*2+1])%MOD;
	}
	
	void pushdown(ll x)
	{
		if(lazy[x])
		{
			ll v=lazy[x]; lazy[x]=0;
			sum[x*2]=mod[v][r[x*2]-l[x*2]+1];
			sum[x*2+1]=mod[v][r[x*2+1]-l[x*2+1]+1];
			lazy[x*2]=lazy[x*2+1]=v;
		}
	}
	
	void update(ll x,ll ql,ll qr,ll v)
	{
		if (l[x]==ql && r[x]==qr)
		{
			sum[x]=mod[v][qr-ql+1];
			lazy[x]=v;
			return;
		}
		pushdown(x);
		ll mid=(l[x]+r[x])>>1;
		if (qr<=mid) update(x*2,ql,qr,v);
		else if (ql>mid) update(x*2+1,ql,qr,v);
		else update(x*2,ql,mid,v),update(x*2+1,mid+1,qr,v);
		sum[x]=(sum[x*2]*power[r[x*2+1]-l[x*2+1]+1]%MOD+sum[x*2+1])%MOD;
	}
}seg;

int main()
{
	scanf("%lld%lld",&n,&Q);
	power[1]=10;
	for (ll i=2;i<=n;i++)
		power[i]=power[i-1]*10%MOD;
	for (ll i=1;i<=9;i++)
	{
		mod[i][1]=i;
		for (ll j=2;j<N;j++)
			mod[i][j]=(mod[i][j-1]*10+i)%MOD;
	}
	seg.build(1,1,n);
	while (Q--)
	{
		ll ql,qr,x;
		scanf("%lld%lld%lld",&ql,&qr,&x);
		seg.update(1,ql,qr,x);
		printf("%lld\n",seg.sum[1]);
	}
	return 0;
}