It is that time of the year when the carrot has to pay tribute to the magical rabbit overlord again! As a gift, the carrot decides to prepare an artfully coloured ribbon. She already has a purple ribbon of length ~N~ and width ~1~, but she wants it to be even more perfect, so she paints some parts of the ribbon blue. More specifically, she does ~Q~ paint strokes, with the ~i~th stroke starting at ~x_i~ units from the left end and ending at ~y_i~ units from the left end, where ~x_i~ and ~y_i~ are both integers. Help her find the total area of purple and blue ribbon!

Constraints

For all subtasks:

~0 \le x_i < y_i \le N~

Subtask 1 [40%]

~1 \le N,Q \le 1\,000~

Subtask 2 [60%]

~1 \le N,Q \le 100\,000~

Input Specification

The first line of input will contain two integers, ~N~ and ~Q~. The following ~Q~ lines will each contain two integers, ~x_i~ and ~y_i~.

Output Specification

Two integers on the same line separated by a space, the first one representing the total purple area, and the second one the blue area.

Sample Input

4 3
0 2
1 2
3 4

Sample Output

1 3

Explanation for Sample Output

In the beginning, we have a purple ribbon of length 4. After the first update, the first half of the ribbon is blue. The second update completely overlaps with the first, so the ribbon does not change. The third update changes the last quarter to blue, so the total blue area is ~3~, and the purple area is ~4-3=1~.