長さ $N$ の数列 $a_1, a_2, \dots, a_N$ がある。最初、すべての $a_i$ は $0$ である。このとき、以下のクエリを使用して数列 $a$ を変化させることができる。

$l \ r \ c$: 数列 $a$ の $l$ 番目から $r$ 番目までの値を $c$ に置き換える。

$Q$ 個のクエリが与えられたとき、$f(U, D, L, R)$ を「$U$ 番目から $D$ 番目までのクエリを順に適用したときの $a_L + a_{L+1} + \dots + a_R$ の値」と定義する。$f$ を複数回実行する場合、各実行は互いに独立であり、以前の $f$ の実行が現在の $f$ の実行に影響を与えることはない。

$$\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$$

を $998\,244\,353$ ($= 119 \times 2^{23} + 1$) で割った余りを計算せよ。$998\,244\,353$ は素数である。

入力

最初の行に整数 $N, Q$ が空白区切りで与えられる。($1 \le N, Q \le 300\,000$)

2行目から $Q$ 行にわたって、$Q$ 個のクエリが1行に1つずつ順に与えられる。$i$ 番目のクエリとして、3つの整数 $l_i, r_i, c_i$ が空白区切りで与えられる。($1 \le l_i \le r_i \le N; 0 \le c_i < 998\,244\,353$)

出力

$$\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$$

を $998\,244\,353$ で割った余りを出力せよ。

入出力例

入力 1

2 2
1 2 1
2 2 2

出力 1

14

入力 2

10 10
10 10 593603443
4 9 993565789
3 8 238321270
7 8 424480868
10 10 556869540
8 10 279674600
7 8 575417117
6 8 948583421
6 6 468656456
4 10 865607491

出力 2

830609277

注記

最初の例の場合、

$f(1, 1, 1, 1) = 1$ $f(1, 1, 1, 2) = 1 + 1 = 2$ $f(1, 1, 2, 2) = 1$ $f(1, 2, 1, 1) = 1$ $f(1, 2, 1, 2) = 1 + 2 = 3$ $f(1, 2, 2, 2) = 2$ $f(2, 2, 1, 1) = 0$ $f(2, 2, 1, 2) = 0 + 2 = 2$ $f(2, 2, 2, 2) = 2$

したがって、答えは $1 + 2 + 1 + 1 + 3 + 2 + 0 + 2 + 2 = 14$ となる。