题目描述

$2$ 行 $N$ 列のマス目があります．上から $i$ 行目，左から $j$ 列目のマスを $(i,j)$ で表します．$(i,j)$ には正整数 $x_{i,j}$ が書かれています．

$2$ つのマスは，辺を共有するときに隣接するといいます．

マス $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$ に書かれている整数の総和として定義します．

$2$ つのマス $X,\ Y$ に対して，$X$ から $Y$ へのパスの重みとしてありうる最小値を $f(X,\ Y)$ と書くことにします．すべてのマスの $2$ つ組 $(X,Y)$ に対する $f(X,\ Y)$ の総和を $998244353$ で割った余りを求めてください．

输入格式

入力は以下の形式で標準入力から与えられます．

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

输出格式

すべてのマスの $2$ つ組 $(X,Y)$ に対する $f(X,\ Y)$ の総和を $998244353$ で割った余りを出力してください．

题目大意

给你一个 $2 \times N$ 的网格图，每个格子上都有一个正整数，定义一条路径的长度为这条路径经过的所有点上的正整数之和。对于两个格子 $X,Y$，令 $f(X,Y)$ 表示 $X$ 到 $Y$ 的所有路径中长度最小的路径的长度，，求所有 $(X,Y)$ 的 $f(X,Y)$ 的和对 $998244353$ 取模的结果。

1
3
5

24

2
1 2
3 4

76

5
1 1000000000 1 1 1
1 1 1 1000000000 1

66714886

提示

制約

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

Sample Explanation 1

次の $4$ 通りの値の総和を求めます． - $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$．