坐标轴上有 $$$n$$$ 段。第$$$i$$$段是$$$[l_i, r_i]$$$。我们将属于第$$$i$$$段的所有整数点的集合表示为$$$S_i$$$。
设 $$$A \cup B$$$ 为两个集合 $$$A$$$ 和 $$$B$$$ 的并集,$$$A \cap B$$$ 为两个集合 $$$A$$$ 和 $$$B$$$ 的交集,$$$A \oplus B$$$ 为 $$$A$$$ 和 $$$B$$$ 的对称差(包含所有元素的集合) $$$A$$$ 的元素和 $$$B$$$ 的所有元素(属于两个集合的元素除外)。
设 $$$[\mathbin{op}_1, \mathbin{op}_2, \dots, \mathbin{op}_{n-1}]$$$ 为数组,其中每个元素为 $$$\cup$$$、$$$\oplus$$$ 或 $$$\cap$$$。在选择该数组的所有 $$$3^{n-1}$$$ 方法中,计算以下值的总和:
$$$$$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$$$$
在此表达式中,$$$|S|$$$ 表示集合$$$S$$$ 的大小。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)。
然后是 $$$n$$$ 行。其中第 $$$i$$$ 包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 3 \cdot 10^5$$$)。
输出
打印一个整数 — $$$|(((S_1\ \mathbin{op}_1\ S_2)\ \mathbin{op}_2\ S_3)\ \mathbin{op}_3\ S_4)\ \dots\ \mathbin{op}_{n-1}\ S_n|$$$ 在所有可能的选择方式上的总和$$$[\mathbin{op}_1、\mathbin{op}_2、\dots、\mathbin{op}_{n-1}]$$$。由于答案可能很大,请打印它对 $$$998244353$$$ 取模。
示例
输入 #1
4 3 5 4 8 2 2 1 9
输出 #1
162
输入 #2
4 1 9 3 5 4 8 2 2
输出 #2
102