最近、RUNはKAISTの $N$ 個のすべての領域のペアの間にケーブルを接続するように依頼された。
領域は2次元平面上の領域として扱う。各領域の境界は、$x$ 軸に平行な2辺と $y$ 軸に平行な2辺を持つ4角形である。言い換えれば、各領域は左下の角を $(x_1^i, y_1^i)$、右上の角を $(x_2^i, y_2^i)$ とする長方形の境界を持つ。領域同士は重なっていてもよい。
安全上の理由から、ケーブルは $x$ 軸または $y$ 軸に沿って敷設しなければならない。したがって、$(x_1, y_1)$ から $(x_2, y_2)$ へのケーブル敷設コストは $|x_1 - x_2| + |y_1 - y_2|$ ウォンである。
領域 $A$ と領域 $B$ を接続するケーブルは、それぞれの領域から1点ずつ、計2点を結ぶ必要がある。
すべての領域のペア $\binom{N}{2}$ について、接続にかかるコストの合計の最小値を求めよ。
すべての $\binom{N}{2}$ 個のペアに対してケーブルを敷設する必要があることに注意せよ。これは例えば、あるケーブルの2つの端点が複数のペアに属している場合であっても、それらのすべてのペアを接続したものとはみなさないことを意味する。
答えは非常に大きくなる可能性があるため、998 244 353 で割った余りを出力せよ。答えは常に非負整数になることが証明できる。
入力
1行目に整数 $N$ が与えられる。
続く $N$ 行の各 $i$ 行目には、スペース区切りで4つの整数 $x_1^i, y_1^i, x_2^i, y_2^i$ が与えられる。これらは $i$ 番目の領域を表す長方形の左下の角と右上の角の位置を示す。
出力
すべてのケーブルを敷設するための最小コストをウォン単位で求め、998 244 353 で割った余りを1つの整数として出力せよ。998 244 353 = 119 × 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$)
入出力例
入力 1
3 1 7 2 9 3 2 8 4 4 3 8 5
出力 1
8
入力 2
4 0 1 2 3 1 0 3 2 3 4 5 6 4 3 6 5
出力 2
8