Имеется последовательность $a_1, a_2, \dots, a_N$ длины $N$. Изначально все $a_i$ равны $0$. Последовательность $a$ можно изменять с помощью следующих запросов:

$l \ r \ c$: изменить значения в последовательности $a$ с $l$-го по $r$-й включительно на $c$.

Пусть дано $Q$ запросов. Определим $f(U, D, L, R)$ как «значение суммы $a_L + a_{L+1} + \dots + a_R$ после последовательного применения запросов с $U$-го по $D$-й». При многократном выполнении $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$ запросов, по одному в строке, в порядке их следования. $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

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

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