#P16460. 三线巡城

三线巡城

题目描述

一座城市被抽象为平面直角坐标系,其中划分了 nn 个需要巡检的矩形区域。所有区域的边都与坐标轴平行,第 ii 个区域的左下角为 (xi,1,yi,1)(x_{i,1},y_{i,1}),右上角为 (xi,2,yi,2)(x_{i,2},y_{i,2})。不同区域之间允许重叠。

现在需要规划三条无限延伸的直线巡检航线,并满足以下要求:

  • 每条航线都与某一条坐标轴平行,且其固定坐标必须是整数。换言之,航线方程只能是 x=ax=a 或 y=ay=a,其中 aa 是 [1,109][1,10^9] 范围内的整数;
  • 三条航线必须两两不同;
  • 每个矩形巡检区域都至少与一条航线相交。航线穿过区域内部或与区域边界重合,均视为相交。

一组方案由选出的三条航线确定。请统计能够覆盖全部巡检区域的方案数量,并将答案对 998 244 353998\,244\,353 取模。

输入格式

第一行一个整数 T T ,表示数据组数。

每组数据第一行一个整数 n n ,表示矩形的数量。

接下来 n n 行,每行四个整数 xi,1,yi,1,xi,2,yi,2 x_{i,1},y_{i,1},x_{i,2},y_{i,2} ,表示一个矩形的顶点坐标。

输出格式

每组数据输出一行,一个整数答案。

样例

样例1

样例输入

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

数据范围与提示

本题采用子任务捆绑测试。

子任务 1 1 ( 2 2 分): n=1 n=1 , ∑n≤200 \sum n\leq 200 ;
子任务 2 2 ( 8 8 分): n=2 n=2 , ∑n≤200 \sum n\leq 200 ;
子任务 3 3 ( 15 15 分): n≤100 n\leq 100 , ∑n≤200 \sum n\leq 200 , xi,2,yi,2≤10 x_{i,2},y_{i,2}\leq 10 ;
子任务 4 4 ( 25 25 分): n≤100 n\leq 100 , ∑n≤200 \sum n\leq 200 ;
子任务 5 5 ( 13 13 分): xi,1 x_{i,1} 都相等, xi,2 x_{i,2} 都相等;
子任务 6 6 ( 17 17 分): xi,1 x_{i,1} 都相等;
子任务 7 7 ( 20 20 分):无特殊限制。

所有数据: 1≤T≤105 1\le T\leq 10^5 , 1≤n≤105 1\leq n\leq 10^5 , 1≤xi,1<xi,2≤109 1\leq x_{i,1}\lt x_{i,2}\leq 10^9 , 1≤yi,1<yi,2≤109 1\leq y_{i,1}\lt y_{i,2}\leq 10^9 , ∑n≤2×105 \sum n\leq 2\times 10^5 。