Se tiene una secuencia $a_1, a_2, \dots, a_N$ de longitud $N$. Inicialmente, todos los $a_i$ son $0$. En este estado, se puede modificar la secuencia $a$ utilizando el siguiente tipo de consulta:

$l \ r \ c$: Cambia los valores de la secuencia $a$ desde la posición $l$ hasta la $r$ por $c$.

Dadas $Q$ consultas, definimos $f(U, D, L, R)$ como "el valor de $a_L + a_{L+1} + \dots + a_R$ después de aplicar secuencialmente las consultas desde la $U$-ésima hasta la $D$-ésima". Si se ejecuta $f$ varias veces, cada ejecución es independiente, por lo que una ejecución previa de $f$ no afecta a la ejecución actual de $f$.

Calcule la suma de $f(U, D, L, R)$ para $1 \le U \le Q$, $U \le D \le Q$, $1 \le L \le N$ y $L \le R \le N$, módulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). $998\,244\,353$ es un número primo.

Entrada

La primera línea contiene dos enteros $N$ y $Q$ separados por un espacio ($1 \le N, Q \le 300\,000$).

A partir de la segunda línea, se proporcionan $Q$ consultas, una por línea, en orden. La $i$-ésima consulta contiene tres enteros $l_i, r_i, c_i$ separados por espacios ($1 \le l_i \le r_i \le N$; $0 \le c_i < 998\,244\,353$).

Salida

Imprima la suma de $f(U, D, L, R)$ para todos los rangos posibles, módulo $998\,244\,353$.

Ejemplos

Entrada 1

2 2
1 2 1
2 2 2

Salida 1

14

Entrada 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

Salida 2

830609277

Nota

Para el primer ejemplo:

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

Por lo tanto, la respuesta es $1 + 2 + 1 + 1 + 3 + 2 + 0 + 2 + 2 = 14$.