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!
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~
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~.
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.
4 3 0 2 1 2 3 4
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~.