You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

赌神 $\mathcal{CYJian}$，他回来了！

题目描述

$\mathcal{tomoo}$ 决定与 $\mathcal{CYJian}$ 进行决斗！

已知 $\mathcal{tomoo}$ 有 $\mathcal{N}$ 张扑克牌，每张扑克牌有一个$\mathcal{RP}$值$\mathcal{A_i}$， $\mathcal{CYJian}$ 有$\mathcal{M}$张扑克牌，每张扑克牌有一个$\mathcal{RP}$值$\mathcal{B_i}$。

$\mathcal{CYJian}$ 与 $\mathcal{tomoo}$ 将会各自从他们的牌里任意取一段连续区间的牌决斗，谁的区间内的牌的$\mathcal{RP}$值的和更大，谁就赢了，请你帮忙求出 $\mathcal{tomoo}$ 赢的概率。

输入格式

• 第一行 $2$ 个正整数 $\mathcal{N,M}$
• 第二行 $N$ 个正整数 $\mathcal{A_i}$
• 第三行 $M$ 个正整数 $\mathcal{B_i}$

输出格式

一个数表示 $\mathcal{tomoo}$ 获胜的概率，如果答案可以表示成 $\frac{P}{Q}$ 的形式,则输出 $\frac{P}{Q}\%998244353$（不懂的左转P3811）

5 5
1 2 3 4 5
1 3 5 7 9

754229067

10 15
7 8 5 1 2 3 6 5 4 1 
52 10 5 6 3 2 1 4 5 8 7 4 5 6 3

181952721

1 1
5
5

0

5 5
1254125 36521421 25362142 12514221 25362142
857412252 36322411 2236232 1254112 36224125

261761853

2 2
2 4
2 5

332748118

提示

样例解释

• 样例 $3$：不管怎么抽都是平均，胜率为 $0$
• 样例 $5$：共有 $9$ 种方案，其中 $3$ 次 tomoo 会赢，胜率为 $1/3$

数据范围

• 对于 $20\%$ 的数据，$0<N,M\le50$
• 对于另外 $20\%$ 的数据，$\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6$
• 对于$100\%$的数据，$0<N,M\le2000,0<A_i,B_i\le10^9$