Description

Along the road outside the school gate, positions are numbered from $0$ to $L$, and at every numbered position there is a tree. A lumberjack removes every tree or sapling continuously from position $A$ to $B$ inclusive (denoted as 0 A B, including $A$ and $B$); fortunately, a planter plants a sapling at every empty hole from position $C$ to $D$ inclusive (denoted as 1 C D, including $C$ and $D$), where an empty hole means a position where the tree has been cut and there is currently no sapling (or a previously planted sapling there has been cut again). After all operations, how many saplings remain outside the school gate? How many saplings that were planted were later cut down?

Input Format

The first line contains two positive integers $L$ and $N$, meaning there were originally $L + 1$ trees outside the campus, and there are $N$ cutting or planting operations.

Each of the following $N$ lines contains three integers, indicating the operation tag and its range.

Output Format

Output two lines. The first line is the number of saplings remaining outside the school gate. The second line is the number of saplings that were planted and then cut down.

10 3
0 2 6
1 1 8
0 5 7

3
2

Hint

For $100\%$ of the testdata, $1 \le L \le 10000$, $1 \le N \le 100$.

Translated by ChatGPT 5