102737: [AtCoder]ABC273 Ex - Inv(0,1)ving Insert(1,0)n

Problem Statement

We have a sequence $A$ consisting of integer pairs. Initially, $A = ( (0, 1), (1, 0) )$.

You may perform the following operation on $A$ as many (possibly zero) times as you want:

• choose adjacent two integer pairs $(a, b)$ and $(c, d)$, and insert $(a + c, b + d)$ between them.

For a sequence $T$ consisting of integer pairs, let us define $f(T)$ as follows:

• let $f(T) =$ (the minimum number of operations required to make every element of $T$ contained in $A$).
  • We say that "every element of $T$ is contained in $A$" if, for all elements $x$ contained in $T$, $x$ is contained in (the set consisting of the elements contained in $A$).
• Here, if there are no such operations, let $f(T) = 0$.

There is a sequence $S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$ consisting of $N$ integer pairs. Here, all elements of $S$ are pairwise distinct.
There are $\frac{N \times (N+1)}{2}$ possible consecutive subarrays $S_{l,r}=((a_l,b_l),(a_{l+1},b_{l+1}),\dots,(a_r,b_r))$ of $S$. Find the sum, modulo $998244353$, of $f(S_{l,r})$ over those subarrays.
Formally, find $\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$, modulo $998244353$.

Constraints

• $1 \le N \le 10^5$
• $0 \le a_i,b_i \le 10^9$
• $a_i \neq a_j$ or $b_i \neq b_j$, if $i \neq j$.

Input

The input is given from Standard Input in the following format:

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\dots$
$a_N$ $b_N$

Output

Print the answer as an integer.

Sample Input 1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

Sample Output 1

3511324

• $f(S_{1,1})=2$.
  • We can make $((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0))$.
• $f(S_{1,2})=5$.
• $f(S_{1,3})=7$.
• $f(S_{2,2})=5$.
• $f(S_{2,3})=7$.
• $f(S_{3,3})=4$.
• $f(S_{5,5})=1000000000 = 10^9$.
• $f(S_{5,6})=1000000000 = 10^9$.
• $f(S_{6,6})=0$.
  • $(0, 1)$ is originally contained in $A$.
• $f(S_{l,r})=0$ for all $S_{l,r}$ not mentioned above.
  • We can prove that $A$ can never contain $(0,0)$ or $(6,3)$ regardless of operations.

Therefore, the sum of $f(S_{l,r})$ is $2000000030 = 2 \times 10^9 + 30$, whose remainder when divided by $998244353$ is $3511324$.

问题描述

我们有一个由整数对组成的序列$A$。初始时，$A = ( (0, 1), (1, 0) )$。

你可以对$A$进行以下操作任意多次（可能是零次）：

• 选择相邻的两个整数对$(a, b)$和$(c, d)$，并在它们之间插入$(a + c, b + d)$。

对于由整数对组成的序列$T$，我们定义$f(T)$如下：

• 令$f(T) =$（使$T$中的每个元素都包含在$A$中所需的最小操作数）。
  • 我们说"序列$T$中的每个元素都包含在$A$中"，如果$T$中包含的所有元素$x$都包含在（由$A$中包含的元素组成的集合）中。
• 在这里，如果没有这样的操作，则令$f(T) = 0$。

存在一个由$N$个整数对组成的序列$S = ((a_1, b_1), (a_2, b_2), \dots, (a_N, b_N))$。在这里，$S$中的所有元素都彼此不同。

$S$的连续子数组有$\frac{N \times (N+1)}{2}$种可能。对于这些子数组，求$f(S_{l,r})$的和，模$998244353$。

正式地说，求$\displaystyle \sum^{N} _ {l=1} \sum^{N} _ {r=l} f(S_{l,r})$，模$998244353$。

约束

• $1 \le N \le 10^5$
• $0 \le a_i,b_i \le 10^9$
• $a_i \neq a_j$或$b_i \neq b_j$，如果$i \neq j$。

输入

输入通过标准输入以以下格式给出：

$N$
$a_1$ $b_1$
$a_2$ $b_2$
$\dots$
$a_N$ $b_N$

输出

打印答案为一个整数。

样例输入 1

7
1 2
3 7
3 5
0 0
1000000000 1
0 1
6 3

样例输出 1

3511324

• $f(S_{1,1})=2$。
  • 我们可以将$((0,1),(1,0)) \rightarrow ((0,1),(1,1),(1,0)) \rightarrow ((0,1),(1,2),(1,1),(1,0))$。
• $f(S_{1,2})=5$。
• $f(S_{1,3})=7$。
• $f(S_{2,2})=5$。
• $f(S_{2,3})=7$。
• $f(S_{3,3})=4$。
• $f(S_{5,5})=1000000000 = 10^9$。
• $f(S_{5,6})=1000000000 = 10^9$。
• $f(S_{6,6})=0$。
  • $(0, 1)$原本就包含在$A$中。
• $f(S_{l,r})=0$对于上述未提及的所有$S_{l,r}$。
  • 我们可以证明，无论执行多少次操作，$A$都无法包含$(0,0)$或$(6,3)$。

因此，$f(S_{l,r})$的和为$2000000030 = 2 \times 10^9 + 30$，将其除以$998244353$的余数为$3511324$。