Dany jest ciąg $a_1, a_2, \dots, a_N$ o długości $N$. Początkowo wszystkie $a_i$ są równe $0$. Możemy zmieniać ciąg $a$ za pomocą następujących zapytań:

$l \ r \ c$: zmień wartości w ciągu $a$ od pozycji $l$ do $r$ na $c$.

Dla danych $Q$ zapytań definiujemy $f(U, D, L, R)$ jako „wartość $a_L + a_{L+1} + \dots + a_R$ po wykonaniu zapytań od $U$ do $D$ w kolejności”. Jeśli $f$ jest wykonywane wielokrotnie, każde wykonanie jest niezależne, co oznacza, że poprzednie wykonania $f$ nie wpływają na bieżące wykonanie $f$.

Oblicz sumę $\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$ ($= 119 \times 2^{23} + 1$). Liczba $998\,244\,353$ jest liczbą pierwszą.

Wejście

W pierwszej linii podane są dwie liczby całkowite $N$ oraz $Q$ oddzielone spacją ($1 \le N, Q \le 300\,000$).

Od drugiej linii następuje $Q$ linii, z których każda zawiera zapytanie w kolejności ich występowania. $i$-te zapytanie składa się z trzech liczb całkowitych $l_i, r_i, c_i$ oddzielonych spacjami ($1 \le l_i \le r_i \le N; 0 \le c_i < 998\,244\,353$).

Wyjście

Wypisz sumę $\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$.

Przykład

Wejście 1

2 2
1 2 1
2 2 2

Wyjście 1

14

Wejście 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

Wyjście 2

830609277

Uwagi

Dla pierwszego przykładu:

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

Zatem wynik to $1+2+1+1+3+2+0+2+2 = 14$.