201295: [AtCoder]ARC129 F - Let's Play Tag

Memory Limit：1024 MB Time Limit：8 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0

Description

Score : $1000$ points

Problem Statement

Snuke and $N+M$ children are standing on a number line.

At time $0$, they are at the following positions.

  • Snuke is at coordinate $0$.
  • $N$ children are at negative coordinates. The $i$-th of them is at coordinate $-L_i$.
  • $M$ children are at positive coordinates. The $i$-th of them is at coordinate $R_i$.

They will now play a game of tag. Specifically, they will do the following actions.

  • Snuke first chooses a string $s$ consisting of $N$ Ls and $M$ Rs. Then, for each $i=1,2,\cdots,N+M$, he does the following.
    • If the $i$-th character of $s$ is L, start moving at a speed of $2$ in the negative direction.
    • If the $i$-th character of $s$ is R, start moving at a speed of $2$ in the positive direction.
    • When having caught a child (by occupying the same coordinate), go to the next $i$, or end the game if $i=N+M$.
  • Every child keeps moving at a speed of $1$ in the direction away from Snuke.

Assume that we have found the time when the game ends for every $s$ that Snuke can choose in the beginning. Find the sum of all those values, modulo $998244353$.

Constraints

  • $3 \leq N,M \leq 250000$
  • $1 \leq L_1 < L_2 < \cdots < L_N < 998244353$
  • $1 \leq R_1 < R_2 < \cdots < R_M < 998244353$
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $M$
$L_1$ $L_2$ $\cdots$ $L_N$
$R_1$ $R_2$ $\cdots$ $R_M$

Output

Print the answer.

Sample Input 1

3 3
1 2 3
1 2 3

Sample Output 1

2748

For example, if $s=$LRRLLR, the game goes as follows.

  • At time $0$: Snuke starts moving in the negative direction.
  • At time $1$: Snuke catches a child at coordinate $-2$ and starts moving in the positive direction.
  • At time $5$: Snuke catches a child at coordinate $6$ and starts moving in the positive direction.
  • At time $6$: Snuke catches a child at coordinate $8$ and starts moving in the negative direction.
  • At time $22$: Snuke catches a child at coordinate $-24$ and starts moving in the negative direction.
  • At time $23$: Snuke catches a child at coordinate $-26$ and starts moving in the positive direction.
  • At time $75$: Snuke catches a child at coordinate $78$ and ends the game.

Sample Input 2

7 5
89789743 196247866 205535557 542612813 782887985 889864096 899373580
539329402 618885430 714090971 717251433 860233092

Sample Output 2

937403116

Input

题意翻译

$\texttt{Snuke}$ 和 $n+m$ 个小孩站在数轴上。 $0$ 时刻，$\texttt{Snuke}$ 站在 $0$ 上，有 $n$ 个小孩站在负半轴，第 $i$ 个站在 $-L_i$；有 $m$ 个小孩站在正半轴，第 $i$ 个站在 $R_i$。 然后他们开始操作： - $\texttt{Snuke}$ 选一个包含 $n$ 个 `L` 和 $m$ 个 `R` 的字符串 $S$。然后对于 $i:1\to n+m$，操作： - - 若 $S_i=$ `L`，$\texttt{Snuke}$ 以 $2/s$ 的速度向左走。 - 若 $S_i=$ `R`，$\texttt{Snuke}$ 以 $2/s$ 的速度向右走。 - 当抓到一个小孩了，就 $i\to i+1$。 - 每个时刻每个小孩背离 $\texttt{Snuke}$ 走 $1$。 计数所有结束时间的和模 $998244353$。

Source/Category

加入题单

算法标签：