CF1781E Rectangle Shrinking

你有一个长为 $10^9$，宽为 $2$ 的矩形网格。 起初，网格上有 $n$ 个矩形，这些矩形的边沿着单元格的边。对于第 $i$ 个矩形，左上角为 $(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$，$\sum n \le 2 \times 10^5$。

多测。 第一行一个正整数 $t$ ($1 \le t \le 10^4$) 表示测试用例的数量。 对于每个测试用例， 第一行一个正整数 $n$ ($1 \le n \le 2 \times 10^5$) 表示初始矩形的个数。 接下来一共 $n$ 行，第 $i$ 行包含四个整数 $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$) 表示矩形左上角和右下角的坐标。

对于每个测试用例，第一行一个整数 $s$ 表示剩余矩形覆盖的最大总面积。 在之后 $n$ 行中，第 $i$ 行输出四个整数表示方案： 如果第 $i$ 个矩形被删除，输出 `0 0 0 0`。 否则，输出第 $i$ 个矩形被替换后的左上角和右下角的新坐标，满足 $u_i \le u'_i \le d'_i \le d_i$，$l_i \le l'_i \le r'_i \le r_i$ 。 如果有多个解，输出任意一种。 ### 样例解释  上图为第一个测试用例的图片。上方为初始矩形，下方为剩余矩形。 翻译来自 [jianhe](https://www.luogu.com.cn/user/613794)。

The picture in the statement illustrates the first test case.