DreamGrid 正在一个 $n$ 行 $m$ 列的网格上创作像素画，所有单元格初始均为白色。作为一名初级像素艺术家，他只能在网格上绘制水平线或垂直线。

我们将第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。形式化地： 一条水平线 $(r, c_1, c_2)$（其中 $c_1 \le c_2$）由所有满足 $i = r$ 且 $c_1 \le j \le c_2$ 的单元格 $(i, j)$ 组成； 一条垂直线 $(c, r_1, r_2)$（其中 $r_1 \le r_2$）由所有满足 $j = c$ 且 $r_1 \le i \le r_2$ 的单元格 $(i, j)$ 组成； * 在网格上绘制一条线后，DreamGrid 会将该线上的所有单元格变为黑色。

一段时间后，DreamGrid 在网格上留下了 $k$ 条互不相交的线。由于 DreamGrid 也是一位竞技编程爱好者，他也对艺术作品的数学性质很感兴趣。

令 $G_i$ 为包含原始 $n \times m$ 网格前 $i$ 行的子网格。我们用 $s_i$ 表示 $G_i$ 中黑色单元格的数量，$c_i$ 表示 $G_i$ 中黑色连通分量的数量。你能帮助 DreamGrid 计算所有 $1 \le i \le n$ 的 $s_i$ 和 $c_i$ 的值，以便他能更深入地了解自己的作品吗？

注意，在本题中，如果存在一个黑色单元格序列 $(r_1, c_1), (r_2, c_2), \dots, (r_k, c_k)$，使得 $r_1 = r_a, c_1 = c_a, r_k = r_b, c_k = c_b$，且对于所有 $1 \le i < k$，$(r_i, c_i)$ 和 $(r_{i+1}, c_{i+1})$ 共享一条边，则称两个黑色单元格 $(r_a, c_a)$ 和 $(r_b, c_b)$ 处于同一个连通分量中。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含三个整数 $n, m$ 和 $k$ ($1 \le n, m, k \le 10^5$)，分别表示网格的行数、列数以及 DreamGrid 绘制的线条数量。

接下来的 $k$ 行，每行包含四个整数 $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$ 或 $c_1 = c_2$)，表示 DreamGrid 在网格上绘制的线条。 $r_1 = r_2$ 表示 DreamGrid 绘制了一条水平线 $(r_1, c_1, c_2)$； $c_1 = c_2$ 表示 DreamGrid 绘制了一条垂直线 $(c_1, r_1, r_2)$； * $r_1 = r_2$ 和 $c_1 = c_2$ 可能同时成立，表示 DreamGrid 将单元格 $(r_1, c_1)$ 涂成了黑色。

保证： 同一组测试数据中，任意两条线互不相交。如果存在一个单元格同时包含在两条线中，则称这两条线相交。 所有测试数据的 $n$ 之和以及 $k$ 之和均不超过 $5 \times 10^5$。注意，题目不保证 $m$ 之和的范围。

输出格式

对于每组测试数据，输出 $n$ 行，其中第 $i$ 行包含两个整数 $s_i$ 和 $c_i$，用空格分隔，分别表示网格前 $i$ 行中黑色单元格的数量和黑色连通分量的数量。

样例

输入 1

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

输出 1

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”。