CF1781E.Rectangle Shrinking

You have a rectangular grid of height $2$ and width $10^9$ consisting of unit cells. There are $n$ rectangles placed on this grid, and the borders of these rectangles pass along cell borders. The $i$-th rectangle covers all cells in rows from $u_i$ to $d_i$ inclusive and columns from $l_i$ to $r_i$ inclusive ($1 \le u_i \le d_i \le 2$; $1 \le l_i \le r_i \le 10^9$). The initial rectangles can intersect, be nested, and coincide arbitrarily.

You should either remove each rectangle, or replace it with any of its non-empty subrectangles. In the latter case, the new subrectangle must lie inside the initial rectangle, and its borders must still pass along cell borders. In particular, it is allowed for the subrectangle to be equal to the initial rectangle.

After that replacement, no two (non-removed) rectangles are allowed to have common cells, and the total area covered with the new rectangles must be as large as possible.

Illustration for the first test case. The initial rectangles are given at the top, the new rectangles are given at the bottom. Rectangle number $4$ is removed.

你有一个高度为 $2$、宽度为 $10^9$ 的矩形网格，由单位格子构成。该网格上放置了 $n$ 个矩形，这些矩形的边界均与格子边界重合。第 $i$ 个矩形覆盖所有行号在 $u_i$ 到 $d_i$（含端点）之间、列号在 $l_i$ 到 $r_i$（含端点）之间的格子（其中 $1 \le u_i \le d_i \le 2$；$1 \le l_i \le r_i \le 10^9$）。初始矩形可以任意相交、嵌套或完全重合。

你需要对每个矩形执行以下两种操作之一：

• 将其移除；
• 或将其替换为它的任意一个非空子矩形。该子矩形必须完全位于原矩形内部，且其边界仍需与格子边界重合。特别地，允许子矩形与原矩形完全相同。

完成上述操作后，任意两个未被移除的矩形不得覆盖任何公共格子，且所有新矩形所覆盖的总格子数应尽可能大。

第一个测试用例示意图。顶部为初始矩形，底部为操作后的新矩形。矩形编号 $4$ 被移除。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of rectangles.

Each of the next $n$ lines contains four integers $u_i, l_i, d_i, r_i$ ($1 \le u_i \le d_i \le 2$; $1 \le l_i \le r_i \le 10^9$) — the coordinates of cells located in the top-left and the bottom-right corners of the rectangle, respectively.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 矩形的数量。

接下来的 $n$ 行中，每行包含四个整数 $u_i, l_i, d_i, r_i$（$1 \le u_i \le d_i \le 2$；$1 \le l_i \le r_i \le 10^9$），分别表示该矩形左上角与右下角单元格的坐标。

保证所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。

For each test case, first print an integer $s$ — the largest possible covered by new rectangles area. Then print $n$ lines with your solution to cover this area.

In the $i$-th of these lines print four integers $u'_i, l'_i, d'_i, r'_i$. If you remove the $i$-th rectangle, print $u'_i = l'_i = d'_i = r'_i = 0$. Otherwise, these numbers denote the new coordinates of the top-left and the bottom-right corners of the $i$-th rectangle, satisfying $u_i \le u'_i \le d'_i \le d_i$; $l_i \le l'_i \le r'_i \le r_i$.

If there are multiple solutions, print any.

对于每个测试用例，首先输出一个整数 $s$ —— 新矩形所能覆盖的最大面积。然后输出 $n$ 行，表示达到该最大覆盖面积的一种方案。

在这些行中的第 $i$ 行，输出四个整数 $u'_i, l'_i, d'_i, r'_i$。若你选择移除第 $i$ 个矩形，则输出 $u'_i = l'_i = d'_i = r'_i = 0$；否则，这四个数表示第 $i$ 个矩形调整后的新坐标，其中 $(u'_i, l'_i)$ 和 $(d'_i, r'_i)$ 分别为其左上角和右下角顶点，且需满足约束：$u_i \le u'_i \le d'_i \le d_i$ 以及 $l_i \le l'_i \le r'_i \le r_i$。

若存在多种可行解，输出任意一种即可。

The picture in the statement illustrates the first test case.

题目描述中的图片展示了第一个测试用例。