연결 케이블

최근 RUN은 KAIST의 $N$개 지역 사이의 모든 쌍을 케이블로 연결하라는 요청을 받았다.

지역은 2차원 평면 위의 영역으로 본다. 각 지역의 경계는 $x$축과 평행한 변 2개, $y$축과 평행한 변 2개로 이루어진 직사각형이다. 지역 $i$는 왼쪽 아래 모서리가 $(x_1^i, y_1^i)$이고 오른쪽 위 모서리가 $(x_2^i, y_2^i)$이다. 지역끼리는 서로 겹칠 수 있다.

안전상의 이유로 케이블은 $x$축 또는 $y$축을 따라 설치해야 한다. 따라서 $(x_1, y_1)$에서 $(x_2, y_2)$까지 케이블을 설치하는 비용은 $\left|x_1-x_2\right|+\left|y_1-y_2\right|$원이다.

지역 $A$와 $B$를 잇는 케이블은 각 지역에서 점을 하나씩 골라 연결한다.

모든 $\binom{N}{2}$개 쌍에 케이블을 하나씩 설치할 때 필요한 총비용의 최솟값을 구하라. 케이블 하나가 여러 쌍을 대신할 수는 없다. 끝점이 여러 쌍에 해당하더라도 마찬가지다.

답이 커질 수 있으므로 $998\,244\,353$으로 나눈 나머지를 출력한다. 답은 항상 0 이상의 정수이다.

첫 줄에 정수 $N$이 주어진다. 이어지는 $N$개 줄의 $i$번째 줄에는 $i$번째 지역의 왼쪽 아래 모서리와 오른쪽 위 모서리 좌표를 나타내는 정수 $x_1^i$, $y_1^i$, $x_2^i$, $y_2^i$가 공백으로 구분되어 주어진다.

모든 케이블의 총비용의 최솟값을 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다. $998\,244\,353 = 119 \times 2^{23} + 1$은 소수이다.

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