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;

const int N=1000010,mod=998244353;
int tag[N<<2],n,a[N],k,ci[N],num[N],ans[N];

#define ls now<<1
#define rs now<<1|1
void psd(int now){
	if(tag[now]){
		ans[ls]=1ll*tag[now]*num[ls]%mod;
		ans[rs]=1ll*tag[now]*num[rs]%mod;
		tag[ls]=tag[now];
		tag[rs]=tag[now];
		tag[now]=0;
	}
}

void pre(int now,int l,int r){
	if(l==r) {ans[now]=num[now]=ci[n-r];return ;}
	int mid=(l+r)/2;
	pre(ls,l,mid);pre(rs,mid+1,r);
	ans[now]=num[now]=(num[ls]+num[rs])%mod;
}

void add(int now,int x,int y,int t,int l=1,int r=n){
	if(l==x && r==y) {
		ans[now]=1ll*t*num[now]%mod;
		tag[now]=t;
		return ;
	}
	psd(now);
	int mid=(l+r)/2;
	if(y<=mid) add(ls,x,y,t,l,mid);
	else if(mid<x) add(rs,x,y,t,mid+1,r);
	else add(ls,x,mid,t,l,mid),add(rs,mid+1,y,t,mid+1,r);
	ans[now]=(ans[ls]+ans[rs])%mod;
}

int main(){
	scanf("%d %d",&n,&k);tag[1]=1;
	int x,y,l,r;
	ci[0]=1;for(int i=1;i<=n;i++) ci[i]=1ll*ci[i-1]*10%mod;
	pre(1,1,n);
	for(int i=1;i<=k;i++)
		scanf("%d %d %d",&x,&y,&l),add(1,x,y,l),printf("%d\n",ans[1]);
}