|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|9 초||512 MB||1||1||1||100.000%|
Fouad wants to eat a chocolate bar, so he bought a rectangular chocolate bar that has N rows and M columns of chocolate.
Fouad found that most of the cells in that chocolate bar are dark chocolate except for K cells which are white chocolate. Now, he wants to eat a prefix sub-grid of the bar. A prefix sub-grid is a rectangular sub-grid that starts at the first cell (1, 1) and ends at any cell (i, j). Fouad is also wondering how many perfect prefix sub-grids of the bar. A perfect prefix sub-grid is a one that contains an odd number of white chocolate cells.
Help Fouad find the number of perfect prefix sub-grids and non-perfect prefix sub-grids.
The first line of the input containing a single integer T specifying the number of test cases.
Each test case begins with a line containing three integers N, M, and K (1 ≤ N, M ≤ 109, 0 ≤ K ≤ 103), in which N and M are the number of rows and columns in the chocolate bar, respectively, and K is the number of white chocolate cells.
Then K lines follow, each line containing two integers Xi and Yi (1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M), giving the positions of the white chocolate cells. It is guaranteed that all the given positions are unique.
For each test case, print a single line containing two space-separated integers representing the number of perfect prefix sub-grids and non-perfect prefix sub-grids, respectively.
3 3 3 0 3 3 1 2 2 5 5 5 1 5 2 1 3 3 4 2 5 4
0 9 4 5 14 11
In the second test case, the chocolate bar can be represented as follows:
ddd dwd ddd
in which ‘d’ represents dark chocolate cells while ‘w’ represents white chocolate cells. There are four perfect prefix sub-grids that end at cells: (2, 2), (2, 3), (3, 2), and (3, 3).