Recientemente, a RUN se le pidió conectar cables entre todos los pares de las $N$ áreas de KAIST.
Tratamos las áreas como regiones en el plano bidimensional. El límite de cada región es un polígono de 4 lados con 2 bordes paralelos al eje $x$ y 2 bordes paralelos al eje $y$. En otras palabras, cada región tiene un límite rectangular con $(x_1^i, y_1^i)$ como esquina inferior izquierda y $(x_2^i, y_2^i)$ como esquina superior derecha. Las regiones pueden solaparse.
Los cables deben construirse a lo largo del eje $x$ o del eje $y$, debido a problemas de seguridad. Por lo tanto, el costo de construir un cable desde $(x_1, y_1)$ hasta $(x_2, y_2)$ es $|x_1 - x_2| + |y_1 - y_2|$ wones.
Un cable que conecta dos áreas $A$ y $B$ debe conectar dos puntos, uno de cada región.
Encuentre la suma mínima del costo para conectar $\binom{N}{2}$ cables entre todos los pares de áreas.
Tenga en cuenta que los cables deben construirse para todos los $\binom{N}{2}$ pares de áreas. Esto significa, por ejemplo, que incluso si los dos puntos finales de un cable pertenecen a más de un par de áreas, no lo consideramos como una conexión para todos esos pares.
Dado que la respuesta puede ser grande, imprímala módulo $998\,244\,353$. Se puede demostrar que la respuesta es siempre un entero no negativo.
Entrada
La primera línea contiene un entero, $N$.
La $i$-ésima de las siguientes $N$ líneas contiene cuatro enteros separados por espacios $x_1^i, y_1^i, x_2^i$ y $y_2^i$, que indican las posiciones de las esquinas inferior izquierda y superior derecha de la región que representa la $i$-ésima área.
Salida
Imprima un solo entero: el costo mínimo para construir todos los cables en unidades de wones, módulo $998\,244\,353$. $998\,244\,353 = 119 \times 2^{23} + 1$ es un número primo.
Restricciones
- $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$)
Ejemplos
Entrada 1
3 1 7 2 9 3 2 8 4 4 3 8 5
Salida 1
8
Entrada 2
4 0 1 2 3 1 0 3 2 3 4 5 6 4 3 6 5
Salida 2
8