有一個長度為 $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$）。

從第二行開始，共有 $Q$ 行，依序給出 $Q$ 個查詢。第 $i$ 個查詢包含三個整數 $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$。