分数: 1000 点
问题陈述
潜伏和 N+M 孩子们站在数轴上。
时间 0,它们位于以下位置。
- Snuke 已到达坐标 0.
- N 孩子们处于负坐标。的 i- 第一个位于坐标处 -L_i.
- M 孩子们位于正坐标。的 i- 第一个位于坐标处 R_i.
他们现在将玩捉人游戏。 具体来说,他们将采取以下行动。
- Snuke 首先选择一个字符串 s 组成 N
L和 MRs。 然后,对于每个 i=1,2,\cdots,N+M,他执行以下操作。- 如果 i- 第一个字符 s is
L,开始以以下速度移动 2 负方向。 - 如果 i- 第一个字符 s is
R,开始以以下速度移动 2 正方向。 - 当抓住一个孩子(通过占据相同的坐标)时,转到下一个 i,或者结束游戏,如果 i=N+M.
- 如果 i- 第一个字符 s is
- 每个孩子都以以下速度移动 1 远离Snuke的方向。
假设我们已经找到了每个游戏结束的时间 Snuke一开始可以选择的 s 。求所有这些值的总和,取模 998244353.
约束
- 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
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M L_1 L_2 \cdots L_N R_1 R_2 \cdots R_M
输出
打印答案。
示例输入 1
3 3 1 2 3 1 2 3
示例输出 1
2748
例如,如果
牌匾上写着 s=LRRLLR,游戏进行如下。
- 时间 0: Snuke 开始向负方向移动。
- 时间 1: Snuke 在坐标处抓住了一个孩子 -2 并开始朝正方向移动。
- 时间 5: Snuke 在坐标处抓住了一个孩子 6 并开始朝正方向移动。
- 时间 6: Snuke 在坐标处抓住了一个孩子 8 并开始向负方向移动。
- 时间 22: Snuke 在坐标处抓住了一个孩子 -24 并开始向负方向移动。
- 时间 23: Snuke 在坐标处抓住了一个孩子 -26 并开始朝正方向移动。
- 时间 75: Snuke 在坐标处抓住了一个孩子 78 并结束游戏。
示例输入 2
7 5 89789743 196247866 205535557 542612813 782887985 889864096 899373580 539329402 618885430 714090971 717251433 860233092
示例输出 2
937403116