Submit solution

Points: 10
Time limit: 1.5s
Memory limit: 256M

Author:
Problem type

Flippers is playing Othello with Desdemona, but with a twist. He wants to win.

Othello is played on a N by N board with pieces that are black on one side and white on the other. Initially, the entire board is black. Flippers decides to be white, and Desdemona is black. Players execute moves in the form x y w h, meaning that they flip all pieces inside w\times h rectangle with the top left vertex at (x, y), provided they are not invariant.

In this twisted Othello game, there is an invariant square in the form X Y L somewhere in the grid, denoting a square of side lengths L with the top left vertex at (X, Y). Pieces inside this square cannot be flipped. In other words, they will stay black so as to give Desdemona an advantage.

In total, Flippers and Desdemona played M moves. However, they don't know what the board looks like! Given the moves, please help them determine the number of white pieces and the number of black pieces on the board.

Constraints

10 \le N \le 2500

1 \le M \le 10^6

Input Specification

The first line will contain integers N and M.

The second line will contain X, Y, and L, (0\le X, Y \le N-1; 1 \le L \le N; 1 \le X+L, Y+L \le N)

The next M lines will contain integers x, y, w, h, (0\le x, y \le N-1; 1 \le w, h \le N; 1 \le x+w, y+h \le N)

Output Specification

Output the number of black pieces and white pieces after M moves, separated by a space.

Sample Input 1

6 1
2 3 3
3 1 3 4

Sample Output 1

28 8

Sample Explanation 1

Here is what the grid looks like:

Sample Input 2

10 4
1 3 4
5 4 1 5
1 0 5 8
7 6 3 3
5 5 5 5

Sample Output 2

65 35

Sample Explanation 2

Here is what the grid looks like:


Comments

There are no comments at the moment.