URI Online Judge | 2241


By Maratona de Programação da SBC – 2016 BR Brazil

Timelimit: 1

Go-- is to like the traditional game of Go, but is much easier! It is played on a square board of size N, initially empty, in which two players, one playing with black stones and the other with white, take turns placing a stone at a time into any cell that is not yet occupied. The game ends after each player put P stones on the board. Consider all possible square sub-areas of size from 1 to N. A sub-area belongs to the player who plays with black stones if it contains at least one black and no white stone stone. Likewise, a square sub-area belongs to the player who plays with white stones contains at least one white stone and no black stone. Note that the areas that contain no stone, or that contain both black as white stones, do not belong to any player.

This problem, given the final position of the board, your program should calculate how many square sub-areas belonging to each player, to find out who won the match. In the figure, black having 12 sub-fields (five dimension 1, six 2 dimensional and one dimension 3). White, who lost the match, have only 10.


The first row entry contains two integers N and P, 2 ≤ N ≤ 500, 1 ≤ P ≤ 500 and P ≤ N2 / 2, representing, respectively, the size of the board and the number of stones that each player places. Each of the following lines P contains two integers L and C (1 L, C ≤ N) setting the coordinates (row, column) of black stones. Then each of the next P lines contains two integers L and C (1 ≤ L, CN) defining the coordinates (row, column) of white stones. All stones are placed in separate cells.


Print a line containing two integers separated by a space: how many different areas belonging to black and white.

Input Samples Output Samples

2 1

1 1

2 2

1 1

5 5

1 3

2 3

2 4

4 1

5 3

1 5

2 1

3 5

4 4

5 1

12 10

500 3

500 498

500 499

500 500

120 124

251 269

499 498

4 12463784