Welcome to ZOJ
Select Problem
ZOJ Problem Set - 4050
Pixel Art

Time Limit: 2 Seconds      Memory Limit: 131072 KB

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, c_1, c_2)$ where $c_1 \le c_2$ consists of all the cells $(i, j)$ satisfying $i = r$ and $c_1 \le j \le c_2$;

  • A vertical line $(c, r_1, r_2)$ where $r_1 \le r_2$ consists of all the cells $(i, j)$ satisfying $j = c$ and $r_1 \le i \le r_2$;

  • 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 $G_i$ be the sub-grid containing the the first $i$ rows of the original $n \times m$ grid. We denote $s_i$ as the number of black cells in $G_i$ and $c_i$ as the number of black connected components in $G_i$. Can you help DreamGrid calculate the value of $s_i$ and $c_i$ for all $1 \le i \le n$, so that he can have a deeper insight into his artwork?

Note that in this problem, two black cells $(r_a, c_a)$ and $(r_b, c_b)$ are in the same connected component, if there exists a sequence of black cells $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$ such that $r_1 = r_a, c_1 = c_a, r_k = r_b, c_k = c_b$ and for all $1 \le i < k$, $(r_i, c_i)$ and $(r_{i+1}, c_{i+1})$ share an edge.


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 \le n, m, k \le 10^5$), 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 $r_1, c_1, r_2, c_2$ ($1 \le r_1 \le r_2 \le n$, $1 \le c_1 \le c_2 \le m$, $r_1 = r_2$ or $c_1 = c_2$) indicating the lines DreamGrid painted on the grid.

  • $r_1 = r_2$ indicates that DreamGrid has painted a horizontal line $(r_1, c_1, c_2)$;

  • $c_1 = c_2$ indicates that DreamGrid has painted a vertical line $(c_1, r_1, r_2)$;

  • It's possible that both $r_1 = r_2$ and $c_1 = c_2$ hold, indicating that DreamGrid has turned the cell $(r_1, c_1)$ 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 \times 10^5$. Note that there is no guarantee on the sum of $m$.


For each test case output $n$ lines where the $i$-th line contains two integers $s_i$ and $c_i$ 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.

Sample Input

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

Sample Output

2 1
5 2
3 1
6 1
3 1
4 1
6 2


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

Author: ZHAO, Yueqi
Source: The 2018 ACM-ICPC Asia Qingdao Regional Contest, Online
Submit    Status