#P18395. Pixel Art

Pixel Art

Pixel Art

DreamGrid 正在一个 nn 行 mm 列的网格上创作像素画。初始所有格子都是白色,他只能画水平或竖直的线段。

记第 ii 行、第 jj 列的格子为 (i,j)(i,j):

  • 水平线段 (r,c1,c2)(r,c_1,c_2)(c1≤c2c_1\le c_2)包含所有满足 i=ri=r 且 c1≤j≤c2c_1\le j\le c_2 的格子。
  • 竖直线段 (c,r1,r2)(c,r_1,r_2)(r1≤r2r_1\le r_2)包含所有满足 j=cj=c 且 r1≤i≤r2r_1\le i\le r_2 的格子。
  • 画一条线段会将这条线段包含的所有格子涂黑。

经过一段时间,他画出了 kk 条互不相交的线段。他还希望研究这幅作品的数学性质。

令 GiG_i 表示原网格的前 ii 行构成的子网格,sis_i 表示 GiG_i 中黑色格子的数量,cic_i 表示 GiG_i 中黑色连通块的数量。请计算所有 1≤i≤n1\le i\le n 对应的 si,cis_i,c_i。

两个黑格属于同一个连通块,当且仅当存在一条完全由黑格组成的路径,从一个格子到达另一个格子,且路径上连续两个格子共享一条边。仅在角上接触不算连通。

输入格式

第一行包含整数 TT,表示测试用例数量。

对于每个测试用例:

  • 第一行包含三个整数 n,m,kn,m,k(1≤n,m,k≤1051\le n,m,k\le10^5)。
  • 接下来 kk 行,每行包含四个整数 r1,c1,r2,c2r_1,c_1,r_2,c_2,表示一条线段。保证 1≤r1≤r2≤n1\le r_1\le r_2\le n,1≤c1≤c2≤m1\le c_1\le c_2\le m,且 r1=r2r_1=r_2 或 c1=c2c_1=c_2。

若 r1=r2r_1=r_2,表示第 r1r_1 行从第 c1c_1 列到第 c2c_2 列的水平线段。若 c1=c2c_1=c_2,表示第 c1c_1 列从第 r1r_1 行到第 r2r_2 行的竖直线段。两个等式可能同时成立,此时线段仅包含一个格子。

保证同一测试用例中的任意两条线段不会包含同一个格子,共享端点格子也算相交。线段之间允许相邻。

保证所有测试用例的 nn 之和不超过 5×1055\times10^5,kk 之和不超过 5×1055\times10^5;不保证 mm 的总和有上界。原题未另给 TT 上限,由 n≥1n\ge1 可知 T≤5×105T\le5\times10^5。

输出格式

对于每个测试用例,输出 nn 行。第 ii 行输出 sis_i 和 cic_i,用一个空格分隔。

样例

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
2 1
5 2
3 1
6 1
3 1
4 1
6 2

样例说明

下面的原图展示了三个测试用例,格子中的数字表示所属线段在该测试用例中的编号。

原题三个样例示意图

第三个测试用例的第一行有 3 个黑格、1 个连通块;前两行有 4 个黑格、1 个连通块;全部三行有 6 个黑格、2 个连通块。因此对应输出为 3 1、4 1、6 2。