分数: 600 点
问题陈述
我们有一套 S of N 点位于二维平面中。的坐标 i第一点是 (x_i, y_i)。的 N 点有明显的 x- 坐标和不同 y- 坐标。
对于非空子集 T of S,让 f(T) 是最小矩形中包含的点数,其边平行于坐标轴,包含 T。更正式地,我们定义 f(T) 如下:
- f(T) := (整数个数 i (1 \leq i \leq N) 这样 a \leq x_i \leq b 和 c \leq y_i \leq d,其中 a, b, c,和 d 是最小值 x- 坐标,最大值 x- 坐标,最小值 y- 坐标,最大 y- 中的点的坐标 T)
求总和 f(T) 所有非空子集 T of S。由于它可能很大,因此打印模数之和 998244353.
约束
- 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)
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N x_1 y_1 : x_N y_N
输出
打印总和 f(T) 所有非空子集 T of S,模数 998244353.
示例输入 1
3 -1 3 2 1 3 -2
示例输出 1
13
设第一点、第二点和第三点为 分别为 P_1, P_2,和 P_3。 S = \{P_1, P_2, P_3\} 有七个非空子集,并且 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.
示例输入 2
4 1 4 2 1 3 3 4 2
示例输出 2
34
示例输入 3
10 19 -11 -3 -12 5 3 3 -15 8 -14 -9 -20 10 -9 0 2 -7 17 6 -6
示例输出 3
7222
请务必打印模数总和 998244353.