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$)

힌트