题目描述

给定一个长度为 $N$ 的字符串 $S$。初始时，$S$ 中的所有字符都是 1。

你将执行 $Q$ 次查询。在第 $i$ 次查询中，你将获得两个整数 $L_i, R_i$ 和一个字符 $D_i$（一个数字）。然后，你必须将第 $L_i$ 到第 $R_i$（包括两端）的字符替换为 $D_i$。

在每次查询之后，将字符串 $S$ 作为十进制整数读取，并打印其对 $998,244,353$ 取模的值。

约束条件

• $1 \leq N, Q \leq 200,000$
• $1 \leq L_i \leq R_i \leq N$
• $1 \leq D_i \leq 9$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $Q$ $L_1$ $R_1$ $D_1$ $:$ $L_Q$ $R_Q$ $D_Q$

输出

打印 $Q$ 行。第 $i$ 行打印第 $i$ 次查询后的 $S$ 的值，对 $998,244,353$ 取模。

样例输入 1

8 5
3 6 2
1 4 7
3 8 3
2 2 2
4 5 1

样例输出 1

11222211
77772211
77333333
72333333
72311333

样例输入 2

200000 1
123 456 7

样例输出 2

641437905

别忘了取模。