AT_arc129_f [ARC129F] Let's Play Tag
题目描述
在数轴上,すぬけくん和 $N+M$ 个孩子站在一起。
在时刻 $0$ 时,他们的位置如下:
- すぬけくん在坐标 $0$。
- $N$ 个孩子站在负方向的位置,第 $i$ 个孩子在坐标 $-L_i$。
- $M$ 个孩子站在正方向的位置,第 $i$ 个孩子在坐标 $R_i$。
现在他们要开始玩捉迷藏。具体规则如下:
- すぬけくん首先从 $N$ 个 `L` 和 $M$ 个 `R` 组成的字符串 $s$ 中选择一个。然后,对于每个 $i=1,2,\cdots,N+M$,执行以下操作:
- 如果 $s$ 的第 $i$ 个字符是 `L`,则以速度 $2$ 向负方向移动。
- 如果 $s$ 的第 $i$ 个字符是 `R`,则以速度 $2$ 向正方向移动。
- 每当すぬけくん抓到一个孩子(即坐标重合)时,立即进行下一个 $i$ 的操作。如果 $i=N+M$,则游戏结束。
- 所有孩子始终以速度 $1$ 向远离すぬけくん的方向移动。
请你对于すぬけくん可以选择的所有字符串 $s$,求出每种情况下游戏结束的时刻,将这些时刻的总和对 $998244353$ 取模后输出。
输入格式
输入以以下格式从标准输入读入:
> $N$ $M$ $L_1$ $L_2$ $\cdots$ $L_N$ $R_1$ $R_2$ $\cdots$ $R_M$
输出格式
请输出答案。
说明/提示
### 限制条件
- $3\leq N,M\leq 250000$
- $1\leq L_1