Connecting Cables

Time limit2sMemory limit1024 MB

Summary

Given N axis-aligned rectangles, find the sum over all pairs of the minimum Manhattan distance between them, modulo 998244353.

Level: Medium6 of 10
Topics: Sorting, Prefix sum
Solved: No attempts yet

Problem

RUN was recently asked to connect cables between every pair of the $N$ areas of KAIST.

Each area is a region on the 2D plane. Its boundary is a rectangle with two edges parallel to the $x$ -axis and two edges parallel to the $y$ -axis. Area $i$ has its lower left corner at $(x_1^i, y_1^i)$ and its upper right corner at $(x_2^i, y_2^i)$ . Areas may overlap.

For safety reasons, cables must run along the $x$ -axis or the $y$ -axis. So the cost of 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 between areas $A$ and $B$ connects one point from each region.

Find the minimum total cost to build all $\binom{N}{2}$ cables, one for each pair of areas. A single cable cannot serve several pairs, even if its endpoints fit more than one pair.

Since the answer can be large, print it modulo $998\,244\,353$ . The answer is always a non-negative integer.

Input

The first line contains an integer $N$ . Each of the next $N$ lines contains four space-separated integers $x_1^i$ , $y_1^i$ , $x_2^i$ , and $y_2^i$ , the coordinates of the lower left and upper right corners of the $i$ -th area.

Output

Print a single integer: the minimum total cost of all cables, modulo $998\,244\,353$ . Note that $998\,244\,353 = 119 \times 2^{23} + 1$ is prime.

Constraints

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

Examples2

Example 1
Input
```
3
1 7 2 9
3 2 8 4
4 3 8 5
```
Expected output
```
8
```
Example 2
Input
```
4
0 1 2 3
1 0 3 2
3 4 5 6
4 3 6 5
```
Expected output
```
8
```