There is a sequence $a$ of length $N$, $a_1, a_2, \dots, a_N$. Initially, all $a_i$ are $0$. You can change the sequence $a$ using the following query:

$l \ r \ c$: Change the values of $a_l, a_{l+1}, \dots, a_r$ to $c$.

Given $Q$ queries, we define $f(U, D, L, R)$ as the value of $a_L + a_{L+1} + \dots + a_R$ after applying the queries from the $U$-th to the $D$-th in order. When $f$ is executed multiple times, each execution is independent, meaning a previous execution of $f$ does not affect the current execution of $f$.

Calculate the sum of $f(U, D, L, R)$ for all $1 \le U \le D \le Q$ and $1 \le L \le R \le N$, modulo $998\,244\,353$ ($= 119 \times 2^{23} + 1$). Note that $998\,244\,353$ is a prime number.

Input

The first line contains two integers $N$ and $Q$ separated by a space ($1 \le N, Q \le 300\,000$).

Starting from the second line, $Q$ queries are given, one per line in order. The $i$-th query consists of three integers $l_i, r_i, c_i$ separated by spaces ($1 \le l_i \le r_i \le N$; $0 \le c_i < 998\,244\,353$).

Output

Output the sum of $f(U, D, L, R)$ for all $1 \le U \le D \le Q$ and $1 \le L \le R \le N$, modulo $998\,244\,353$.

Examples

Input 1

2 2
1 2 1
2 2 2

Output 1

14

Input 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

Output 2

830609277

Note

For the first example:

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

Therefore, the answer is $1 + 2 + 1 + 1 + 3 + 2 + 0 + 2 + 2 = 14$.