Récemment, RUN a été chargé de connecter des câbles entre toutes les paires des $N$ zones de KAIST.
Nous traitons les zones comme des régions sur un plan bidimensionnel. La frontière de chaque région est un polygone à 4 côtés avec 2 arêtes parallèles à l'axe des $x$ et 2 arêtes parallèles à l'axe des $y$. En d'autres termes, chaque région possède une frontière rectangulaire avec $(x_1^i, y_1^i)$ comme coin inférieur gauche et $(x_2^i, y_2^i)$ comme coin supérieur droit. Les régions peuvent se chevaucher.
Les câbles doivent être construits le long de l'axe des $x$ ou de l'axe des $y$ pour des raisons de sécurité. Ainsi, le coût de construction d'un câble reliant $(x_1, y_1)$ à $(x_2, y_2)$ est $|x_1 - x_2| + |y_1 - y_2|$ wons.
Un câble reliant deux zones $A$ et $B$ doit connecter deux points, un de chaque région.
Trouvez la somme minimale du coût pour connecter $\binom{N}{2}$ câbles entre toutes les paires de zones.
Notez que les câbles doivent être construits pour toutes les $\binom{N}{2}$ paires de zones. Cela signifie, par exemple, que même si deux extrémités d'un câble appartiennent à plus d'une paire de zones, nous ne considérons pas qu'il connecte toutes ces paires.
Comme la réponse peut être grande, affichez-la modulo $998\,244\,353$. Il peut être prouvé que la réponse est toujours un entier non négatif.
Entrée
La première ligne contient un entier, $N$.
La $i$-ième des $N$ lignes suivantes contient quatre entiers séparés par des espaces $x_1^i, y_1^i, x_2^i$ et $y_2^i$ — indiquant les positions des coins inférieur gauche et supérieur droit de la région représentant la $i$-ième zone.
Sortie
Affichez un seul entier — le coût minimal pour construire tous les câbles en wons, modulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ est un nombre premier.
Contraintes
- $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$)
Exemples
Entrée 1
3 1 7 2 9 3 2 8 4 4 3 8 5
Sortie 1
8
Entrée 2
4 0 1 2 3 1 0 3 2 3 4 5 6 4 3 6 5
Sortie 2
8