Bajtazar is preparing to paint a fence. He has already prepared $n$ cans of white paint, which he has placed in a row and numbered from $1$ to $n$. He would like to use this paint, but he does not want to paint the fence white. He has hired color-mixing specialists who have three dyes at their disposal: yellow, blue, and red. They performed $m$ operations, where the $i$-th operation consisted of adding a certain dye to all cans between the $l_i$-th and $r_i$-th inclusive.
The resulting color of the paint depends on the set of dyes that have been added to it at least once. The dyes mix according to the following table and diagram:
| Dyes | Color |
|---|---|
| none | white |
| yellow | yellow |
| blue | blue |
| red | red |
| yellow + blue | green |
| yellow + red | orange |
| blue + red | violet |
| yellow + blue + red | brown |
Bajtazar would like to paint the fence with a single color. After some thought, he chose green, as it reminds him of the "OK" or "Accepted" verdict that one can sometimes see in algorithmic competitions. He wonders how many cans of paint now have this color. Help him and count it!
Input
The first line of the input contains two integers $n$ and $m$ ($1 \le n, m \le 10^6$), representing the number of cans in the row and the number of operations performed by the paint-mixing specialists, respectively.
Each of the next $m$ lines contains three integers $l_i$, $r_i$, and $k_i$ ($1 \le l_i \le r_i \le n$, $1 \le k_i \le 3$), indicating that the $i$-th operation consisted of adding a dye to the cans from $l_i$ to $r_i$ inclusive, and this dye was yellow ($k_i = 1$), blue ($k_i = 2$), or red ($k_i = 3$).
Output
The output should contain a single integer representing the number of cans with green paint after all operations are completed.
Examples
Input 1
9 5 2 8 1 4 5 2 6 7 3 5 6 2 1 2 2
Output 1
3
Note
Explanation of the example: The paint in the consecutive cans is: blue, green, yellow, green, green, brown, orange, yellow, and white. Therefore, the green color appears in three cans.