题目描述

我们有一个 $2$ 行 $N$ 列的网格。设 $(i,j)$ 表示位于从上往下的第 $i$ 行、从左往右的第 $j$ 列的方格。$(i,j)$ 上写着一个正整数 $x_{i,j}$。

当两个方格共享一条边时，我们称它们是相邻的。

从方格 $X$ 到方格 $Y$ 的路径是一个由不同的方格构成的序列 $(P_1, \ldots, P_n)$，满足 $P_1 = X$，$P_n = Y$，且对每个 $1\leq i \leq n-1$，$P_i$ 和 $P_{i+1}$ 是相邻的。此外，该路径的权重是方格 $P_1, \ldots, P_n$ 上整数的和。

对于两个方格 $X$ 和 $Y$，记 $f(X,Y)$ 为从 $X$ 到 $Y$ 的最小权重路径。求所有方格对 $(X,Y)$ 的 $f(X,Y)$ 的和，对 $998244353$ 取模。

约束条件

• $1\leq N\leq 2\times 10^5$
• $1\leq x_{i,j} \leq 10^9$

输入

从标准输入读入数据，格式如下：

$N$ $x_{1,1}$ $\ldots$ $x_{1,N}$ $x_{2,1}$ $\ldots$ $x_{2,N}$

输出

输出所有方格对 $(X,Y)$ 的 $f(X,Y)$ 的和，对 $998244353$ 取模。

示例一

1
3
5

示例一输出

24

您需要计算以下四个值的和。

• 对于 $X = (1,1), Y = (1,1)$：$f(X,Y) = 3$。
• 对于 $X = (1,1), Y = (2,1)$：$f(X,Y) = 8$。
• 对于 $X = (2,1), Y = (1,1)$：$f(X,Y) = 8$。
• 对于 $X = (2,1), Y = (2,1)$：$f(X,Y) = 5$。

示例二

2
1 2
3 4

示例二输出

76

示例三

5
1 1000000000 1 1 1
1 1 1 1000000000 1

示例三输出

66714886