[EC Final 2022] Rectangle

**【题目描述】** 庞教授有 $n$ 个矩形，第 $i$ 个矩形的左下角坐标是 $(x_{i,1}, y_{i,1})$，右上角坐标是 $(x_{i,2}, y_{i,2})$。矩形可以重叠。 你需要选择三条直线，使得： - 每条直线应该与 $x$ 轴或 $y$ 轴平行，即其方程为 $x = a$ 或 $y = a$。 - 在方程 $x = a$ 或 $y = a$ 中，$a$ 应该是 $[1, 10^9]$ 区间内的整数。 - 这三条直线应该是不同的。 - 每个矩形至少被一条直线 $\textbf{触摸}$。如果一条直线与矩形的边界和/或内部相交，则称该直线触摸该矩形。 你需要计算选择三条直线的方法数。由于答案可能非常大，输出对 $998244353$ 取模的结果。如果两种方法只有三条直线的顺序不同，则认为它们是相同的。 **【输入格式】** 第一行包含一个整数 $T~(1 \le T \le 10^5)$，表示测试用例的数量。 对于每个测试用例，第一行包含一个整数 $n~(1 \le n \le 10^5)$。接下来的 $n$ 行中，第 $i$ 行包含四个整数 $x_{i,1}, y_{i,1},x_{i,2}, y_{i,2}~(1\le x_{i,1}<x_{i,2}\le 10^9,1\le y_{i,1}<y_{i,2}\le 10^9)$。 保证所有测试用例中 $n$ 的总和不超过 $2\times 10^5$。 **【输出格式】** 对于每个测试用例，输出一行整数，表示答案。 **【样例解释】** 翻译来自于：[ChatGPT](https://chatgpt.com/)

Prof. Pang has $n$ rectangles, the coordinate of the lower left corner of the $i$-th rectangle is $(x_{i,1}, y_{i,1})$, and the coordinate of the upper right corner is $(x_{i,2}, y_{i,2})$. Rectangles may overlap. You need to choose three straight lines such that: - Each line should be parallel to the $x$-axis or the $y$-axis, which means its formula is $x = a$ or $y = a$. - In the formula $x = a$ or $y = a$, $a$ should be an integer in $[1, 10^9]$. - These three lines should be distinct. - Each rectangle is $\textbf{touched}$ by at least one line. A line touches a rectangle if it intersects with the boundary and/or the interior of the rectangle. You need to compute the number of ways to choose three lines. Since the answer can be very large, output it modulo $998244353$. Two ways are considered the same if only the order of three lines differs in these two ways.

The first line contains a single integer $T~(1 \le T \le 10^5)$, denoting the number of test cases. For each test case, the first line contains an integer $n~(1 \le n \le 10^5)$. The $i$-th line of the next $n$ lines contains four integers $x_{i,1}, y_{i,1},x_{i,2}, y_{i,2}~(1\le x_{i,1}<x_{i,2}\le 10^9,1\le y_{i,1}<y_{i,2}\le 10^9)$. It is guaranteed that the sum of $n$ over all test cases does not exceed $2\times 10^5$.

For each test case, output one integer representing the answer in one line.

3
1
1 1 1000000000 1000000000
3
1 1 2 2
3 3 4 4
5 5 6 6
5
581574116 47617804 999010750 826131769
223840663 366320907 613364068 926991396
267630832 51913575 488301124 223957497
217461197 492085159 999485867 913732845
28144453 603781668 912516656 993160442

230616300
64
977066618