题目描述

给定长度为 $N$ 的整数序列 $A=(A_1,A_2,\cdots,A_N)$、$B=(B_1,B_2,\cdots,B_N)$、$X=(X_1,X_2,\cdots,X_N)$、$Y=(Y_1,Y_2,\cdots,Y_N)$。其中，$A$ 和 $B$ 满足以下性质：

• $A_1=1$。
• $B_1=2$。
• $(A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N)$ 是 $(1,2,\cdots,2N)$ 的一个排列。

定义整数 $d_{i,j}$（$1\leq i,j\leq N$）如下：

• $d_{1,1}=0$。
• 当 $(i,j)\neq (1,1)$ 且 $A_i < B_j$ 时：$d_{i,j}=d_{i,j-1}+X_i$。
• 当 $(i,j)\neq (1,1)$ 且 $A_i > B_j$ 时：$d_{i,j}=d_{i-1,j}+Y_j$。

请计算 $\sum_{1\leq i\leq N}\sum_{1\leq j\leq N}d_{i,j}$，并输出其对 $998244353$ 取模的结果。

输入格式

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

$N$ $A_1$ $A_2$ $\cdots$ $A_N$ $B_1$ $B_2$ $\cdots$ $B_N$ $X_1$ $X_2$ $\cdots$ $X_N$ $Y_1$ $Y_2$ $\cdots$ $Y_N$

输出格式

输出答案。

样例 1

输入

2
1 4
2 3
2 2
1 3

输出

8

样例 2

输入

3
1 3 5
2 6 4
1 10 100
1000 10000 100000

输出

108153

样例 3

输入

3
1 6 5
2 4 3
1 10 100
1000 10000 100000

输出

333009

样例 4

输入

10
1 17 4 7 16 18 9 3 12 6
2 19 20 14 5 11 13 8 15 10
744280520 249168130 239276621 320064892 910500852 164832983 245532751 198319687 715892722 967824729
769431650 80707350 459924868 257261830 777045524 583882654 950300099 438099970 322288793 532405020

输出

746075419

说明/提示

限制条件

• $2\leq N\leq 250000$。
• $A_1=1$。
• $B_1=2$。
• $(A_1,A_2,\cdots,A_N,B_1,B_2,\cdots,B_N)$ 是 $(1,2,\cdots,2N)$ 的一个排列。
• $1\leq X_i\leq 10^9$。
• $1\leq Y_i\leq 10^9$。
• 输入的所有值均为整数。

样例解释 1

$d_{i,j}$ 的值如下：

• $d_{1,1}=0$
• $d_{1,2}=d_{1,1}+X_1=0+2=2$
• $d_{2,1}=d_{1,1}+Y_1=0+1=1$
• $d_{2,2}=d_{1,2}+Y_2=2+3=5$

因此，所求答案为 $0+2+1+5=8$。

由 ChatGPT 4.1 翻译