Soit une suite $a_1, a_2, \dots, a_N$ de longueur $N$. Initialement, tous les $a_i$ sont égaux à $0$. On peut modifier la suite $a$ en utilisant la requête suivante :

$l \ r \ c$ : remplace les valeurs de la suite $a$ du $l$-ième au $r$-ième élément par $c$.

Étant donné $Q$ requêtes, on définit $f(U, D, L, R)$ comme « la valeur de $a_L + a_{L+1} + \dots + a_R$ après avoir appliqué les requêtes de la $U$-ième à la $D$-ième dans l'ordre ». Si $f$ est exécuté plusieurs fois, chaque exécution est indépendante, de sorte que l'exécution précédente de $f$ n'affecte pas l'exécution actuelle de $f$.

Calculez la somme suivante modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$) : $$\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$$ $998\,244\,353$ est un nombre premier.

Entrée

La première ligne contient deux entiers $N$ et $Q$ séparés par un espace ($1 \le N, Q \le 300\,000$).

À partir de la deuxième ligne, $Q$ lignes suivent, chacune contenant une requête. La $i$-ième requête contient trois entiers $l_i, r_i, c_i$ séparés par des espaces ($1 \le l_i \le r_i \le N$; $0 \le c_i < 998\,244\,353$).

Sortie

Affichez la somme $\sum_{U=1}^{Q} \sum_{D=U}^{Q} \sum_{L=1}^{N} \sum_{R=L}^{N} f(U, D, L, R)$ modulo $998\,244\,353$.

Exemples

Entrée 1

2 2
1 2 1
2 2 2

Sortie 1

14

Entrée 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

Sortie 2

830609277

Remarque

Pour le premier exemple :

$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$

Par conséquent, la réponse est $1 + 2 + 1 + 1 + 3 + 2 + 0 + 2 + 2 = 14$.