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;

#define INF 1234567890
#define ll long long
#define MOD 998244353

int N, Q;
ll pw[270000], V[10][270000];
ll seg[530000], lazy[530000];

void Propagate(int n, int l, int r)
{
	if (lazy[n] != -1)
	{
		if (l != r)
		{
			lazy[n<<1] = lazy[n];
			lazy[n<<1|1] = lazy[n];
		}
		seg[n] = V[lazy[n]][r-l+1];
		lazy[n] = -1;
	}
}

ll Update(int L, int R, int val, int n, int l, int r)
{
	Propagate(n, l, r);
	if (r < L || R < l) return seg[n];
	if (L <= l && r <= R)
	{
		lazy[n] = val;
		Propagate(n, l, r);
		return seg[n];
	}
	int mid = l+r>>1;
	ll le = Update(L, R, val, n<<1, l, mid);
	ll ri = Update(L, R, val, n<<1|1, mid+1, r);
	return seg[n] = (le*pw[r-mid]+ri)%MOD;
}

int main()
{
	memset(lazy, -1, sizeof(lazy));

	pw[0] = 1;
	for(int i=1; i<270000; i++)
	{
		pw[i] = pw[i-1] * 10 % MOD;
		for(int k=0; k<10; k++)
		{
			V[k][i] = (V[k][i-1]*10 + k) % MOD;
			// V[9][3] = 999
		}
	}

	scanf("%d %d", &N, &Q);
	Update(1, N, 1, 1, 1, N);
	while(Q--)
	{
		int L, R, D;
		scanf("%d %d %d", &L, &R, &D);
		Update(L, R, D, 1, 1, N);
		printf("%lld\n", seg[1]);
	}
	return 0;
}