Background

God of Gambling $\mathcal{CYJian}$ is back!

Problem Description

$\mathcal{tomoo}$ decides to duel with $\mathcal{CYJian}$!

It is known that $\mathcal{tomoo}$ has $\mathcal{N}$ playing cards, and each card has an $\mathcal{RP}$ value $\mathcal{A_i}$. $\mathcal{CYJian}$ has $\mathcal{M}$ playing cards, and each card has an $\mathcal{RP}$ value $\mathcal{B_i}$.

$\mathcal{CYJian}$ and $\mathcal{tomoo}$ will each choose an arbitrary contiguous interval of cards from their own decks to duel. Whoever has the larger sum of $\mathcal{RP}$ values within their chosen interval wins. Please help compute the probability that $\mathcal{tomoo}$ wins.

Input Format

• The first line contains two positive integers $\mathcal{N,M}$.
• The second line contains $N$ positive integers $\mathcal{A_i}$.
• The third line contains $M$ positive integers $\mathcal{B_i}$.

Output Format

Output one number representing the probability that $\mathcal{tomoo}$ wins. If the answer can be written in the form $\frac{P}{Q}$, then output $\frac{P}{Q}\%998244353$ (if you do not understand, see 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

Hint

Sample Explanation

• Sample $3$: No matter how you choose, the result is always a tie on average, so the win rate is $0$.
• Sample $5$: There are $9$ possible ways in total, and tomoo wins $3$ times, so the win rate is $1/3$.

Constraints

• For $20\%$ of the testdata, $0<N,M\le50$.
• For another $20\%$ of the testdata, $\sum_{i=1}^NA_i\le10^6,\sum_{j=1}^MB_j\le10^6$.
• For $100\%$ of the testdata, $0<N,M\le2000,0<A_i,B_i\le10^9$.

Translated by ChatGPT 5