拉马赞决定从事一项严肃的生意——种植卷心菜。

种植卷心菜的田地是一个无限大的网格。网格中的每个单元格都可以种植一颗卷心菜。

拉马赞只在田地的一部分进行了种植。他计划使用若干个矩形区域，但结果发现其中一些区域可能会重叠。如果一个单元格位于至少一个矩形内，则该单元格属于种植区域。

形式上，拉马赞选择了 $n$ 个矩形区域 $(x_i^L, y_i^L, x_i^R, y_i^R)$ ($x_i^L \le x_i^R, y_i^L \le y_i^R, 1 \le i \le n$)。如果存在至少一个选定的矩形 $i$ ($1 \le i \le n$)，使得 $x_i^L \le x \le x_i^R$ 且 $y_i^L \le y \le y_i^R$，则单元格 $(x, y)$ 包含卷心菜。

拉马赞过去是一名程序员（也是一名获胜者），因此他决定使用人工智能机器人来定期处理种植区域。一个机器人可以服务于任意的水平单元格段 $(x_1^{robot}, x_2^{robot}, y^{robot})$，即所有满足 $x_1^{robot} \le x \le x_2^{robot}$ 且 $y = y^{robot}$ 的单元格 $(x, y)$。

重要的是，机器人只能在有种植的区域内行驶。他意识到，为了最小化机器人的数量，使用无法扩展的水平段非常重要。

如果满足以下条件，拉马赞将在单元格段 $(x_1^{robot}, x_2^{robot}, y^{robot})$ 上使用机器人：

• 所有满足 $x_1^{robot} \le x \le x_2^{robot}$ 且 $y = y^{robot}$ 的单元格 $(x, y)$ 都属于种植区域；
• 单元格 $(x_1^{robot} - 1, y^{robot})$ 不属于种植区域；
• 单元格 $(x_2^{robot} + 1, y^{robot})$ 不属于种植区域。

你的任务是收集关于将在种植园工作的机器人的重要统计数据。我们称一对 $(x_1, x_2)$ 在行 $y$ 被服务，如果存在一个机器人恰好在段 $(x_1, x_2, y)$ 上工作。

• 找出所有在某一行被服务的对 $(x_1, x_2)$。
• 对于每一对 $(x_1, x_2)$，找出它被服务的行数。
• 对于每一对 $(x_1, x_2)$，找出它被服务的最大连续行数。换句话说，找出最大的整数 $k$，使得存在一段 $k$ 个连续的行 $[y_1, y_2]$ ($y_2 - y_1 + 1 = k$)，对于任意行 $y_1 \le y \le y_2$，对 $(x_1, x_2)$ 都在行 $y$ 被服务。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 200\,000$) —— 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 200\,000$) —— 选定矩形区域的数量。

接下来的 $n$ 行，每行包含四个整数 $x_i^L, y_i^L, x_i^R, y_i^R$ ($1 \le x_i^L \le x_i^R \le 10^9, 1 \le y_i^L \le y_i^R \le 10^9$) —— 选定矩形区域的描述。

记 $N$ 为单个测试中所有测试用例的 $n$ 之和。保证 $N \le 200\,000$。

输出格式

对于每个测试用例，首先输出一个整数 $p$ ($p \ge 1$) —— 在某一行被服务的对 $(x_1, x_2)$ 的数量。

在接下来的 $p$ 行中，每行输出四个整数 $x_1, x_2, cnt, k$ ($1 \le x_1 \le x_2 \le 10^9, 0 \le cnt, k \le 10^9$)。$cnt$ 应等于对 $(x_1, x_2)$ 被服务的行数。$k$ 应等于对 $(x_1, x_2)$ 被服务的最大连续行数。

所有对 $(x_1, x_2)$ 必须不同。每一对在某一行被服务的对必须恰好输出一次。可以以任意顺序输出这些对。

样例

样例输入 1

4
2
2 2 3 3
3 3 4 4
2
2 1 2 3
1 2 3 2
4
2 2 4 5
3 4 9 7
2 9 9 10
7 1 9 7
7
2 1 2 9
5 1 6 8
4 5 7 6
1 8 4 10
1 6 3 6
1 2 7 3
4 1 7 1

样例输出 1

3
2 3 1 1
2 4 1 1
3 4 1 1
2
1 3 1 1
2 2 2 1
4
2 4 2 2
2 9 4 2
3 9 2 2
7 9 3 3
6
1 4 2 2
1 6 1 1
1 7 3 2
2 2 4 2
4 7 2 1
5 6 2 1

说明

第一个和第二个测试用例的说明

在第一个测试用例中，机器人将在段 $(2, 3, 2), (2, 4, 3), (3, 4, 4)$ 上工作。因此，对 $(2, 3), (2, 4), (3, 4)$ 在某一行被服务，且每一对恰好在其中一行被服务。

在第二个测试用例中，机器人将在段 $(2, 2, 1), (2, 4, 2), (2, 2, 3)$ 上工作。因此，对 $(2, 2), (2, 4)$ 在某一行被服务。对 $(2, 2)$ 在第 1 行和第 3 行被服务，对 $(2, 4)$ 在第 2 行被服务。

第三个和第四个测试用例的说明