시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.

예제 입력 1

3
3 3 0
3 3 1
2 2
5 5 5
1 5
2 1
3 3
4 2
5 4

예제 출력 1

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).