D. Pixel Art
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

DreamGrid is creating a piece of pixel art on a grid of n rows and m columns where all the cells are initially white. As a beginner pixel artist, he can only paint horizontal or vertical lines on the grid.

Let's denote the cell on the i-th row and the j-th column as (i, j). Formally speaking,

  • A horizontal line (r, c1, c2) where c1 ≤ c2 consists of all the cells (i, j) satisfying i = r and c1 ≤ j ≤ c2;
  • A vertical line (c, r1, r2) where r1 ≤ r2 consists of all the cells (i, j) satisfying j = c and r1 ≤ i ≤ r2;
  • By painting a line on the grid, DreamGrid will turn all the cells in that line into black cells.

After some time, DreamGrid has left k non-intersecting lines on the grid. As DreamGrid is also an enthusiast for competitive programming, he is interested in the mathematical properties of his artwork as well.

Let Gi be the sub-grid containing the the first i rows of the original n × m grid. We denote si as the number of black cells in Gi and ci as the number of black connected components in Gi. Can you help DreamGrid calculate the value of si and ci for all 1 ≤ i ≤ n, so that he can have a deeper insight into his artwork?

Note that in this problem, two black cells (ra, ca) and (rb, cb) are in the same connected component, if there exists a sequence of black cells (r1, c1), (r2, c2), ..., (rk, ck) such that r1 = ra, c1 = ca, rk = rb, ck = cb and for all 1 ≤ i < k, (ri, ci) and (ri + 1, ci + 1) share an edge.

Input

There are multiple test cases. The first line of the input contains an integer T, indicating the number of test cases. For each test case:

The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 105), indicating the number of rows and the number of columns of the grid, and the number of lines DreamGrid has painted.

The following k lines each contains four integers r1, c1, r2, c2 (1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 ≤ m, r1 = r2 or c1 = c2) indicating the lines DreamGrid painted on the grid.

  • r1 = r2 indicates that DreamGrid has painted a horizontal line (r1, c1, c2);
  • c1 = c2 indicates that DreamGrid has painted a vertical line (c1, r1, r2);
  • It's possible that both r1 = r2 and c1 = c2 hold, indicating that DreamGrid has turned the cell (r1, c1) to a black cell.

It's guaranteed that

  • No two lines in the same test case will intersect. Two lines intersect if there exists a cell which is contained in both lines;
  • Neither the sum of n nor the sum of k of all test cases will exceed 5 × 105. Note that there is no guarantee on the sum of m.
Output

For each test case output n lines where the i-th line contains two integers si and ci separated by a space, indicating the number of black cells and the number of black connected components in the first i rows of the grid.

Example
Input
3
2 5 2
1 1 1 2
2 3 2 5
2 5 2
1 1 1 3
2 3 2 5
3 3 3
1 1 1 2
3 1 3 2
1 3 2 3
Output
2 1
5 2
3 1
6 1
3 1
4 1
6 2
Note

The following image illustrates the sample test cases. The number in the cell indicates the index of the corresponding line.

For the third sample test case, it's obvious that there are 3 black cells and 1 black connected components in the first row, 4 black cells and 1 black connected components in the first two rows, and 6 black cells and 2 black connected components in all the three rows. So the answer is "3 1", "4 1" and "6 2".