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 <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lc(p) p+p+1
#define rc(p) p+p+2
#define md(s,e) (s+e)/2

int n,k;
int A[300005];
int Max[300005*4];
int H[300005*4];
int mo = 998244353;
int po[300005];
int D[11][300005];

void mod( int p, int s, int e, int l, int r, int v ){
	if ( s > r || e < l ) return;
	if ( l <= s && e <= r ){
		Max[p] = v;
		H[p] = D[v][e-s+1];
		return;
	}
	int m = md(s,e);
	if ( Max[p] != 0 ){
		Max[lc(p)] = Max[p];
		Max[rc(p)] = Max[p];
		H[lc(p)] = D[Max[p]][m-s+1];
		H[rc(p)] = D[Max[p]][e-m];
		Max[p] = 0;
	}
	mod(lc(p),s,m,l,r,v);
	mod(rc(p),m+1,e,l,r,v);
	H[p] = (H[lc(p)] * 1LL * po[e-m]) % mo;
	H[p] = ( H[p] + H[rc(p)]) % mo;
}

int main(){

	po[0] = 1;
	for ( int i = 1; i <= 200000; i++ ){
		po[i] = (po[i-1] * 1LL * 10 ) % mo;
	}
	scanf("%d%d",&n,&k);
	Max[0] = 1;

	for ( int i = 1; i <= 9; i++ ){
		D[i][0] = 0;
		for ( int j = 1; j <= n; j++ ){
			D[i][j] = ( D[i][j-1] * 1LL * 10 + i ) % mo;
		}
	}
	H[0] = D[1][n];
	for ( int i = 0; i < k; i++ ){
		int l, r, d;
		scanf("%d%d%d",&l,&r,&d);
		mod(0,1,n,l,r,d);
		printf("%d\n",H[0]);
	}
	return 0;
}