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 fast ios::sync_with_stdio(false);cin.tie(NULL)  
#define fi first  
#define se second  
#define all(v) (v).begin(),(v).end()  
#define pb push_back  
#define eb emplace_back
#define em emplace
#define mp make_pair
  
typedef long long ll;  
typedef pair<int,int> pii;  
typedef pair<ll,ll> pll;  
const long long INF = 1e18;  
const int inf = 1e9;
const ll Mod = 998244353;

int n, q;

ll p[200010];
ll dp[200010];
ll tree[800010];
ll lazy[800010];

void propagate(int node, int s, int e) {
	if(!lazy[node]) return;

	tree[node] = (dp[e] - dp[s-1] + Mod) % Mod * lazy[node] % Mod;

	if(s != e) {
		lazy[node*2] = lazy[node*2+1] = lazy[node];
	}

	lazy[node] = 0;
}

void update(int node, int s, int e, int l, int r, int x) {
	propagate(node, s, e);
	if(r < s || e < l) return;
	if(l <= s && e <= r) {
		lazy[node] = x;
		propagate(node, s, e);
		return;
	}

	update(node*2, s, (s+e)/2, l, r, x);
	update(node*2+1, (s+e)/2+1, e, l, r, x);

	tree[node] = (tree[node*2] + tree[node*2+1]) % Mod;
}

int main() {
	fast;

	cin >> n >> q;

	for(int i=1; i<=n; i++) {
		dp[i] = (dp[i-1] * 10 + 1) % Mod;
	}

	update(1, 1, n, 1, n, 1);

	while(q--) {
		int l, r, d;
		cin >> l >> r >> d;

		update(1, 1, n, n - r + 1, n - l + 1, d); 

		cout << tree[1] << "\n";
	}
}