25728번 - Connecting Cables 다국어

Recently, RUN was asked to connect cables between all pairs of the $N$ areas of KAIST.

We treat the areas as regions on the $2$-dimensional plane. The boundary of each region is a $4$-sided polygon with $2$ edges parallel to the $x$-axis, and $2$ edges parallel to the $y$-axis. In other words, each region has a rectangular boundary with $(x_1^i,y_1^i)$ as a lower left corner and $(x_2^i,y_2^i)$ as a upper right corner. The regions may overlap.

The cables must be constructed along the $x$-axis or the $y$-axis, due to safety issues. So the cost of constructing a cable from $(x_1,y_1)$ to $(x_2,y_2)$ is $\left |x_1-x_2\right |+\left |y_1-y_2\right |$ won.

A cable connecting two areas $A$ and $B$ should connect two points, one from each region.

Find the minimum sum of the cost for connecting $\binom{N}{2}$ cables between all pairs of the areas.

Note that the cables must be constructed for all $\binom{N}{2}$ pairs of areas. This means, for example, even if two endpoints of a cable belong to more than one pair of areas, we do not consider it as connecting all such pairs.

Since the answer can be large, output it modulo $998\, 244\, 353$. It can be proved that the answer is always a non-negative integer.

The first line contains one integer, $N$.

The $i$-th of the following $N$ lines contain space-separated four integers $x_1^i$, $y_1^i$, $x_2^i$, and $y_2^i$ — indicating the positions of the lower left and the upper right corners of the region representing the $i$-th area.

Output a single integer — the minimum cost to construct all cables in the unit of won, modulo $998\, 244\, 353$. $998\, 244\, 353=119\times 2^{23}+1$ is a prime number.

• $2\le N\le 300\, 000$
• $0\le x_1^i<x_2^i\le 998\, 244\, 352$ ($1\le i\le N$)
• $0\le y_1^i<y_2^i\le 998\, 244\, 352$ ($1\le i\le N$)