問題文

長さ $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$ の値を modulo $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

あまりをとるのを忘れないでください。