Masha and two friends
Contest: Codeforces Round 524 (Div. 2)
Difficulty rating: 1500
Tags: implementation

Recently, Masha was presented with a chessboard with a height of $$$n$$$ and a width of $$$m$$$.

The rows on the chessboard are numbered from $$$1$$$ to $$$n$$$ from bottom to top. The columns are numbered from $$$1$$$ to $$$m$$$ from left to right. Therefore, each cell can be specified with the coordinates $$$(x,y)$$$, where $$$x$$$ is the column number, and $$$y$$$ is the row number (do not mix up).

Let us call a rectangle with coordinates $$$(a,b,c,d)$$$ a rectangle lower left point of which has coordinates $$$(a,b)$$$, and the upper right one — $$$(c,d)$$$.

The chessboard is painted black and white as follows:

An example of a chessboard.

Masha was very happy with the gift and, therefore, invited her friends Maxim and Denis to show off. The guys decided to make her a treat — they bought her a can of white and a can of black paint, so that if the old board deteriorates, it can be repainted. When they came to Masha, something unpleasant happened: first, Maxim went over the threshold and spilled white paint on the rectangle $$$(x_1,y_1,x_2,y_2)$$$. Then after him Denis spilled black paint on the rectangle $$$(x_3,y_3,x_4,y_4)$$$.

To spill paint of color $$$color$$$ onto a certain rectangle means that all the cells that belong to the given rectangle become $$$color$$$. The cell dyeing is superimposed on each other (if at first some cell is spilled with white paint and then with black one, then its color will be black).

Masha was shocked! She drove away from the guests and decided to find out how spoiled the gift was. For this, she needs to know the number of cells of white and black color. Help her find these numbers!

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^3$$$) — the number of test cases.

Each of them is described in the following format:

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 10^9$$$) — the size of the board.

The second line contains four integers $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ ($$$1 \le x_1 \le x_2 \le m, 1 \le y_1 \le y_2 \le n$$$) — the coordinates of the rectangle, the white paint was spilled on.

The third line contains four integers $$$x_3$$$, $$$y_3$$$, $$$x_4$$$, $$$y_4$$$ ($$$1 \le x_3 \le x_4 \le m, 1 \le y_3 \le y_4 \le n$$$) — the coordinates of the rectangle, the black paint was spilled on.

Output format:
Output $$$t$$$ lines, each of which contains two numbers — the number of white and black cells after spilling paint, respectively.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Explanation for examples:

The first picture of each illustration shows how the field looked before the dyes were spilled. The second picture of each illustration shows how the field looked after Maxim spoiled white dye (the rectangle on which the dye was spilled is highlighted with red). The third picture in each illustration shows how the field looked after Denis spoiled black dye (the rectangle on which the dye was spilled is highlighted with red).

In the first test, the paint on the field changed as follows:

In the second test, the paint on the field changed as follows:

In the third test, the paint on the field changed as follows:

In the fourth test, the paint on the field changed as follows:

In the fifth test, the paint on the field changed as follows:

Example input:
5
2 2
1 1 2 2
1 1 2 2
3 4
2 2 3 2
3 1 4 3
1 5
1 1 5 1
3 1 5 1
4 4
1 1 4 2
1 3 4 4
3 4
1 2 4 2
2 1 3 3

Example output:
0 4
3 9
2 3
8 8
4 8

Editorial:
At first let's define a function $$$w(a,b)$$$, which returns the number of white cells on the subrectangle, the left bottom corner of which has coordinates $$$(1,1)$$$ and the top right one has coordinates $$$(a,b)$$$. (I will tell you how to implement the function later).
How do we solve the problem using this function?
Let's define functions $$$W(a,b,c,d)$$$ and $$$B(a,b,c,d)$$$, which return the number of white cells on the subrectangle which has coordinates $$$(a,b,c,d)$$$ and the number of black cells on the subrectangle which has coordinates $$$(a,b,c,d)$$$. (The definition of what we call the coordinates of a rectangle can be found in the statements)
It can be easily proven that
$$$$$$W(a,b,c,d) = w(c,d) - w(a - 1, d) - w(c, b - 1) + w(a - 1, b - 1)$$$$$$
The value of $$$B(a,b,c,d)$$$ can be found as the number of all cells substracted by the number of the white cells:
$$$$$$B(a,b,c,d) = (c - a + 1) \cdot (d - b + 1) - W(a,b,c,d)$$$$$$
It means that in order to calculate the value of functions $$$W$$$ and $$$B$$$ efficiently it is enough to be able to calculate the value of $$$w$$$ efficiently.
How de solve the problem using the funcitons defined above?
Step 1. We should find the number of black cells and white cells in the initial chessboard (these values will be stored in the variables called $$$black$$$ and $$$white$$$ respectivly):
$$$$$$black = B(1,1,m,n)$$$$$$ $$$$$$white = W(1,1,m,n)$$$$$$
Step 2. All the black cells in the rectangle $$$(x_1,y_1,x_2,y_2)$$$ will become white. So now:
$$$$$$black := black - B(x_1,y_1,x_2,y_2)$$$$$$ $$$$$$white := white + B(x_1,y_1,x_2,y_2)$$$$$$
Step 3. Now all the white cells in the rectangle $$$(x_3,y_3,x_4,y_4)$$$ will become black. So now:
$$$$$$white := white - W(x_3,y_3,x_4,y_4)$$$$$$ $$$$$$black := black + W(x_3,y_3,x_4,y_4)$$$$$$
But since the functions functions $$$B$$$ and $$$W$$$ return the number of cells black and white cells respectively in the initial board, so it isn't enough. What we did in the intersection of the rectangles:
On step 2 we took the cells that were initially black and coloured them in white (everything is ok by now), but on step 3 we took only the cells that were initially white and coloured them in black. The cells that were initially black and coloured in white on step 2 were not coloured in black.
In order to fix this we should find the rectangle which is an intersection of the rectangles $$$(x_1,y_2,x_2,y_2)$$$ and $$$(x_3,y_3,x_4,y_4)$$$, find the number of black cells in it and then colour them in black.
It is obvious that the coordinates of the itersection of the rectangle are $$$(max(x_1,x_3), max(y_1,y_3), min(x_2,x_4), min(y_2, y_4))$$$.
If $$$max(x_1,x_3) > min(x_2,x_4)$$$ or $$$max(y_1,y_3) > min(y_2, y_4)$$$ then there is no intersection, so we can just terminate the program.
In another case we should apply:
$$$$$$white := white - B(max(x_1,x_3), max(y_1,y_3), min(x_2,x_4), min(y_2, y_4))$$$$$$ $$$$$$black := black + B(max(x_1,x_3), max(y_1,y_3), min(x_2,x_4), min(y_2, y_4))$$$$$$
So we solved the task. Now it's time to tell how to implement function $$$w(a,b)$$$.
Let's consider following chessboards from the examples:
In order to explain more easily, I will name the pattern like this the pattern type 1
And the pattern like this the pattern type 2:
It can be easily seen that if the number of rows is even, then the number of rows of both types is equal to $$$\frac{b}{2}$$$.If the number of rows is odd, then the number of rows of the type 2 is equal to $$$\Bigl\lceil \frac{b}{2} \Bigr\rceil$$$ and the number of rows of the type 1 is equal to $$$\Bigl\lfloor \frac{b}{2} \Bigr\rfloor$$$.
Since $$$\Bigl\lceil \frac{b}{2} \Bigr\rceil = \Bigl\lfloor \frac{b}{2} \Bigr\rfloor$$$ if $$$b$$$ is even then we can just assume that the number of rows with pattern type 1 is $$$\Bigl\lfloor \frac{b}{2} \Bigr\rfloor$$$ and the number of rows with pattern type 2 is $$$\Bigl\lceil \frac{b}{2} \Bigr\rceil$$$.
In the same way we can prove that the number of white cells in one row with pattern type 1 is equal to $$$\Bigl\lfloor \frac{a}{2} \Bigr\rfloor$$$ and in the pattern type 2 it is equal to $$$\Bigl\lceil \frac{a}{2} \Bigr\rceil$$$.
So now:
$$$$$$w(a,b) = \Biggl\lceil \frac{b}{2} \Biggr\rceil \cdot \Biggl\lceil \frac{a}{2} \Biggr\rceil + \Biggl\lfloor \frac{b}{2} \Biggr\rfloor \cdot \Biggl\lfloor \frac{a}{2} \Biggr\rfloor$$$$$$
Overall complexity $$$O(1)$$$.