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 ll long long
ll s[800001], mod = 998244353, t[200001], o[10][200001], la[800001];
void upd(ll id, ll l, ll r, ll v){
	s[id] = o[v][r - l + 1];
	la[id] = v;
}
void prop(ll id, ll l, ll r){
	if (la[id] != 0){
		ll mid = (l + r) / 2;
		upd(id * 2, l, mid, la[id]);
		upd(id * 2 + 1, mid + 1, r, la[id]);
		la[id] = 0;
	}
}
void build(ll id, ll l, ll r){
	if (l == r){
		s[id] = 1;
		return;
	}
	ll mid = (l + r) / 2;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	(s[id] = s[id * 2] * t[r - mid] % mod + s[id * 2 + 1]) %= mod;
}
void update(ll id, ll l, ll r, ll L, ll R, ll v){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		upd(id, l, r, v);
		return;
	}
	prop(id, l, r);
	ll mid = (l + r) / 2;
	update(id * 2, l, mid, L, R, v);
	update(id * 2 + 1, mid + 1, r, L, R, v);
	(s[id] = s[id * 2] * t[r - mid] % mod + s[id * 2 + 1]) %= mod;
}
int main(){
	t[0] = 1;
	for (ll i = 1; i < 200001; i++) t[i] = t[i - 1] * 10 % mod;
	for (ll i = 0; i < 10; i++){
		for (ll j = 1; j < 200001; j++) (o[i][j] = o[i][j - 1] * 10 + i) %= mod;
	}
	ll n, q, x, y, z;
	scanf("%lld %lld", &n, &q);
	build(1, 0, n - 1);
	for (int i = 0; i < q; i++){
		scanf("%lld %lld %lld", &x, &y, &z);
		update(1, 0, n - 1, x - 1, y - 1, z);
		printf("%lld\n", s[1]);
	}
}