Problem Description

This problem is translated from PA 2020 Round 1 Mieszanie kolorów.

Byteasar is getting ready to paint a fence. He has prepared $n$ cans of white paint, arranged in a row and numbered from $1$ to $n$. He wants to use these paints, but he does not want to paint the fence white. He hired a color-mixing expert who has three pigments: yellow, blue, and red. The expert performs $m$ operations; in the $i$-th operation, a certain pigment is added to all cans with indices from $l_i$ to $r_i$ (inclusive).

The final color of a paint can depends on which pigments have been added to it. The pigments are mixed according to the following table and illustration.

Byteasar wants to paint the fence a single color. After thinking it over, he chose green, because green stands for the Accepted result you often see in programming contests. He wants to know how many cans of paint are green now. Please help him count them.

Input Format

The first line contains two integers $n, m$, representing the number of paint cans and the number of operations performed by the expert.

The next $m$ lines each contain three integers $l_i, r_i, k_i$, meaning that in the $i$-th operation, a pigment is added to all cans with indices from $l_i$ to $r_i$ (inclusive). The added pigment is yellow ($k_i = 1$), blue ($k_i = 2$), or red ($k_i = 3$).

Output Format

Output one integer on a single line, the number of cans that are green after all operations.

9 5
2 8 1
4 5 2
6 7 3
5 6 2
1 2 2

3

Hint

Explanation of Sample 1

After the operations, the paints are blue, green, yellow, green, green, brown, orange, yellow, and white. Therefore, only three cans of paint are green.

Constraints

This problem uses bundled testdata.

For $100\%$ of the data, it is guaranteed that $1 \le n, m \le 10^6$, $1 \le l_i \le r_i \le n$, and $1 \le k_i \le 3$.

Translated by ChatGPT 5