题目描述

$2$ 次元平面上の $N$ 個の点からなる集合 $S$ があり、$i$ 番目の点の座標は $(x_i,\ y_i)$ です。$N$ 個の点の $x$ 座標、$y$ 座標はそれぞれ相異なります。

$S$ の空でない部分集合 $T$ に対して $f(T)$ を、各辺が座標軸と平行であって $T$ の点を全て含むような最小の長方形に含まれる点の個数として定義します。より正確には、

• $f(T)\ :=\ T$ に含まれる点について $x$ 座標の最小値と最大値を それぞれ $a,\ b$, そして $y$ 座標の最小値と最大値をそれぞれ $c,\ d$ としたとき、$a\ \leq\ x_i\ \leq\ b$ かつ $c\ \leq\ y_i\ \leq\ d$ を満たす $1\ \leq\ i\ \leq\ N$ の個数

$S$ の空でない全ての部分集合 $T$ についての $f(T)$ の和を計算してください。答えは非常に大きくなることがあるので、$998244353$ で割った余りを出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

$S$ の空でない全ての部分集合 $T$ についての $f(T)$ の和を $998244353$ で割った余りを出力せよ。

题目大意

在平面上有 $n$ 个初始点（均为整点），我们定义一个点集的权值为平面上包含这个点集的最小矩形所包含的初始点个数（矩形的边与坐标轴平行），求所有非空点集的权值和，保证每个点的横纵坐标互不相同。

$1 \le N \le 2 \times 10^5$。

$-10^9 \le X_i, Y_i \le 10^9$。

3
-1 3
2 1
3 -2

13

4
1 4
2 1
3 3
4 2

34

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

7222

提示

制約

• $1\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $-10^9\ \leq\ x_i,\ y_i\ \leq\ 10^9$
• $x_i\ \neq\ x_j\ (i\ \neq\ j)$
• $y_i\ \neq\ y_j\ (i\ \neq\ j)$
• 入力は全て整数である

Sample Explanation 1

$1,\ 2,\ 3$ 番目の点をそれぞれ $P_1,\ P_2,\ P_3$ とします。$S\ =\ \{P_1,\ P_2,\ P_3\}$ の空でない部分集合は $7$ 個あり、それぞれに対する $f$ の値は次の通りです。 - $f(\{P_1\})\ =\ 1$ - $f(\{P_2\})\ =\ 1$ - $f(\{P_3\})\ =\ 1$ - $f(\{P_1,\ P_2\})\ =\ 2$ - $f(\{P_2,\ P_3\})\ =\ 2$ - $f(\{P_3,\ P_1\})\ =\ 3$ - $f(\{P_1,\ P_2,\ P_3\})\ =\ 3$ これらの和は $13$ です。

Sample Explanation 3

和を $998244353$ で割った余りを出力することに注意してください。