P11115 [ROI 2024] 白菜 (Day 1)

翻译自 [ROI 2024 D1T4](https://neerc.ifmo.ru/school/archive/2023-2024/ru-olymp-roi-2024-day1.pdf)。 拉马赞决定从事一个重要的业务——种植白菜。种植白菜的场地是一个无限大的网格场地。每个网格单元可以种植一个白菜。拉马赞只种植了场地的一部分。他计划利用其中的几个矩形区域，这些矩形可能会相交。如果一个网格单元位于至少一个矩形内，则该单元被认为种植了白菜。 具体地，拉马赞选择了 $n$ 个矩形区域，矩形的坐标为 $(x_{L_i}, y_{L_i}, x_{R_i}, y_{R_i})$ (其中 $x_{L_i} \le x_{R_i}$，$y_{L_i} \le y_{R_i}$，$1 \le i \le n$)。如果存在至少一个矩形 $i$ ($1 \le i \le n$)，使得 $x_{L_i} \le x \le x_{R_i}$ 且 $y_{L_i} \le y \le y_{R_i}$，则认为网格单元 $(x, y)$ 被种植了白菜。  拉马赞曾经是一个程序员（并且还是一个获奖者），因此他决定使用人工智能机器人定期处理种植。一个机器人可以服务于任意的水平区域 $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$，即所有满足 $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ 且 $y = y_{\text{robot}}$ 的网格单元 $(x, y)$。 重要的是，机器人只能在种植的区域内移动。他明白，为了最小化机器人的数量，需要使用那些不能进一步扩展的水平区域。如果满足以下条件，拉马赞将使用机器人在网格单元 $(x_{\text{robot}_1}, x_{\text{robot}_2}, y_{\text{robot}})$ 上工作： - 所有满足 $x_{\text{robot}_1} \le x \le x_{\text{robot}_2}$ 且 $y = y_{\text{robot}}$ 的网格单元 $(x, y)$ 都属于种植区域； - 网格单元 $(x_{\text{robot}_1} - 1, y_{\text{robot}})$ 不属于种植区域； - 网格单元 $(x_{\text{robot}_2} + 1, y_{\text{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)$ 都被服务。

输入包含多组数据。第一行给出一个整数 $t$（$1 \le t \le 200000$），表示测试数据的组数。 每组数据的第一行给出一个整数 $n$（$1 \le n \le 200000$），表示矩形区域的数量。 接下来的 $n$ 行中，每行包含四个整数 $x_{L_i}$，$y_{L_i}$，$x_{R_i}$，$y_{R_i}$（$1 \le x_{L_i} \le x_{R_i} \le 10^9$，$1 \le y_{L_i} \le y_{R_i} \le 10^9$），表示一个矩形区域。 令 $N$ 表示所有数据集中的 $n$ 总和，保证 $N \le 200000$。

对于每组数据，首先输出一个整数 $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)$ 对，必须输出且只能输出一次。输出顺序可以是任意的。

 在第一组数据中，机器人在以下区段进行服务：$(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$ 行中被服务。 下面是第三和第四组数据的图片。  - 如果你的程序错误地找出了在某一行中被服务的对 $(x_1, x_2)$ 的集合，该测试点将获得零分。 - 如果你的程序： - 能够正确找出该集合，但不是所有的 $cnt$ 都正确，该测试点将获得 $50\%$ 的分数。 - 能够正确找出该集合和所有 $cnt$，但不是所有的 $k$ 都正确，该测试点将获得 $75\%$ 的分数。 - 能够正确找出该集合、所有 $cnt$ 和所有 $k$，该测试点将获得 $100\%$ 的分数。 请注意，如果你想获得获得部分分，仍需为每对配对 $(x_1, x_2)$ 输出一些 $cnt$ 和 $k$ 值，但不必全部正确。