Problem Statement

There is a $2$-dimensional plane, and you want to move from your current coordinates $(0, 0)$ to the destination coordinates $(N, N)$.
When you are at cell $(r, c)$, you can perform the following $2$ types of moves.

• Basically, pay $1$ yen and move from cell $(r, c)$ to cell $(r+1, c)$. This move can be used when $r < N$.
• Basically, pay $1$ yen and move from cell $(r, c)$ to cell $(r, c+1)$. This move can be used when $c < N$.

However, the following $M$ moves alone can be performed for free. (Conversely, note that these moves cannot be performed by paying $1$ yen.)

• When $t_i = 1$: the move from cell $(x_i, y_i)$ to cell $(x_i + 1, y_i)$ can be performed for free.
• When $t_i = 2$: the move from cell $(x_i, y_i)$ to cell $(x_i, y_i + 1)$ can be performed for free.

Input

$N$ $M$
$t_1$ $x_1$ $y_1$
$t_2$ $x_2$ $y_2$
$t_3$ $x_3$ $y_3$
 $\vdots$
$t_M$ $x_M$ $y_M$

Output

Output the answer.

Constraints

• $1 \leq N \leq 200000$
• $0 \leq M \leq 200000$
• $1 \leq t_i \leq 2$
• When $t_i = 1$, $0 \leq x_i < N$ and $0 \leq y_i \leq N$
• When $t_i = 2$, $0 \leq x_i \leq N$ and $0 \leq y_i < N$
• $(t_1, x_1, y_1), (t_2, x_2, y_2), (t_3, x_3, y_3), \dots, (t_N, x_N, y_N)$ are pairwise distinct
• All input values are integers

Sample

Sample 1

Input

2 1
1 0 0

Output

21

As shown in the figure below, there are $6$ ways to move. The total amount is $3 + 3 + 3 + 4 + 4 + 4 = 21$ yen.

5 0

2520

400 10
2 73 190
2 351 261
1 164 365
1 62 221
1 18 209
1 358 211
2 32 206
1 147 46
1 36 77
2 5 203

85571926