Page $1$ of $2$

DMOPC $\text{'}17$ Contest $4$ P$1-$ Ribbon Colouring Fun

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 and width $,$ but she wants

it to be even more perfect, so she paints some parts of the ribbon blue. More specifically, she does paint strokes, with

the th stroke starting at units from the left end and ending at units from the left end, where and are both

integers. Help her find the total area of purple and blue ribbon!

Constraints

For all subtasks:

Subtask $1[40\%]$

Subtask $2[60\%]$

Input Specification

The first line of input will contain two integers, and $.$ The following lines will each contain two integers, and $.$

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

$43$

$02$

$12$

$34$

Sample Output

Time limit: $2\mathrm{.}0$s Memory limit: $64$M

N $1$

Q

i xi yi xi yi

$0<=$ xi $<$ yi $<=$ N

$1<=$ N$,$ Q $<=1000$

$1<=$ N$,$ Q $<=100000$

N Q Q xi yi

Page $2$ of $2$

$13$

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 $43=1.$