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 JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.SortedMap;
import java.util.TreeMap;

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] sa = br.readLine().split(" ");
		int n = Integer.parseInt(sa[0]);
		int q = Integer.parseInt(sa[1]);
		int[] l = new int[q];
		int[] r = new int[q];
		int[] d = new int[q];
		for (int i = 0; i < q; i++) {
			sa = br.readLine().split(" ");
			r[i] = n - Integer.parseInt(sa[0]) + 1;
			l[i] = n - Integer.parseInt(sa[1]);
			d[i] = Integer.parseInt(sa[2]);
		}
		br.close();

		int mod = 998244353;
		long[][] dp = new long[10][n];
		for (int i = 1; i < 10; i++) {
			dp[i][0] = i;
		}
		for (int i = 1; i < n; i++) {
			dp[1][i] = dp[1][i - 1] * 10 % mod;
		}
		for (int i = 1; i < n; i++) {
			dp[1][i] += dp[1][i - 1];
		}
		for (int i = 2; i < 10; i++) {
			for (int j = 1; j < n; j++) {
				dp[i][j] = dp[i - 1][j] + dp[1][j];
				dp[i][j] %= mod;
			}
		}

		PrintWriter pw = new PrintWriter(System.out);
		long ans = dp[1][n - 1];
		TreeMap<Integer, Integer> map = new TreeMap<>();
		map.put(0, 1);
		for (int i = 0; i < q; i++) {
			SortedMap<Integer, Integer> sm = map.subMap(l[i], r[i]);
			Integer ok = map.lowerKey(l[i]);
			if (ok == null) {
				ok = l[i];
			}
			int ov = map.get(ok);
			ok = l[i];
			for (int key : sm.keySet()) {
				if (key > 0) {
					ans -= dp[ov][key - 1];
				}
				if (ok > 0) {
					ans += dp[ov][ok - 1];
				}
				ok = key;
				ov = sm.get(key);
			}
			ans -= dp[ov][r[i] - 1];
			if (ok > 0) {
				ans += dp[ov][ok - 1];
			}
			sm.clear();
			map.put(l[i], d[i]);
			if (!map.containsKey(r[i])) {
				map.put(r[i], ov);
			} else if (map.get(r[i]) == d[i]) {
				map.remove(r[i]);
			}
			ans += dp[d[i]][r[i] - 1];
			if (l[i] > 0) {
				ans -= dp[d[i]][l[i] - 1];
			}
			ans %= mod;
			if (ans < 0) {
				ans += mod;
			}
			pw.println(ans);
		}
		pw.flush();
	}
}