E. 狭窄通道
每个测试点时间限制：$1$ 秒
每个测试点内存限制：$1024$ 兆字节

你是 ICPC 王国的战略家。你收到情报，王国附近的狭窄通道将遭受怪物袭击。该狭窄通道可以表示为一个有 $2$ 行（编号 $1$ 到 $2$）和 $N$ 列（编号 $1$ 到 $N$）的网格。用 $(r,c)$ 表示第 $r$ 行第 $c$ 列的格子。每个格子 $(r,c)$ 每天由一名能力值为 $P_{r,c}$ 的士兵负责守卫。

据悉，通道非常雾大。每天，通道的每一列有 $50\%$ 的概率被雾覆盖。如果一列被雾覆盖，则该列的两名士兵当天不会被部署；否则，士兵会被部署。

定义连通区域 $[u,v]$（$u \le v$）为连续列 $u$ 到 $v$（包含两端）的最大集合，使得该集合中的每一列都没有被雾覆盖。下图是连通区域的示例。灰色单元格表示被雾覆盖的单元格。共有 $4$ 个连通区域：$[1,2]$、$[4,6]$、$[9,9]$ 和 $[11,11]$。

（此处应有示意图，但文本无法显示）

一个连通区域 $[u,v]$ 的强度计算如下：设 $m_1$ 和 $m_2$ 分别为该连通区域内第一行和第二行士兵能力值的最大值，即

$$m_r = \max(P_{r,u}, P_{r,u+1}, \dots, P_{r,v}) \quad (r \in \{1,2\}) $$

若 $m_1 = m_2$，则强度为 $0$；否则，强度为 $\min(m_1, m_2)$。

部署的总强度为所有连通区域的强度之和。求任意一天中总强度的期望值。

输入
第一行一个整数 $N$（$1 \le N \le 100000$）。
接下来两行，每行 $N$ 个整数 $P_{r,c}$（$1 \le P_{r,c} \le 200000$）。

输出
令 $M = 998244353$。可以证明期望总强度可以表示为不可约分数 $\frac{x}{y}$，其中 $x$ 和 $y$ 是整数且 $y \not\equiv 0 \pmod{M}$。输出一行一个整数 $k$，满足 $0 \le k < M$ 且 $k \cdot y \equiv x \pmod{M}$。

样例

输入

3
8 4 5
5 4 8

输出

249561092

输入

5
10 20 5 8 5
5 20 7 5 8

输出

811073541

样例解释

对于样例 #1：
共有 $8$ 种可能的通道状态。每种状态等概率发生。因此期望总强度为

$$(0 + 5 + 10 + 5 + 5 + 0 + 5 + 0) / 8 = \frac{15}{4} $$

由于 $249561092 \cdot 4 \equiv 15 \pmod{998244353}$，因此输出 $249561092$。

对于样例 #2：
期望总强度为 $\frac{671}{6}$。