F - Let's Play Tag Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

数直線上に，すぬけくんと 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 で割った余りを求めてください．

制約

  • 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: すぬけくんが負の方向へ移動を開始する．
  • 時刻 1: すぬけくんが座標 -2 で子供を捕まえた後，正の方向へ移動を開始する．
  • 時刻 5: すぬけくんが座標 6 で子供を捕まえた後，正の方向へ移動を開始する．
  • 時刻 6: すぬけくんが座標 8 で子供を捕まえた後，負の方向へ移動を開始する．
  • 時刻 22: すぬけくんが座標 -24 で子供を捕まえた後，負の方向へ移動を開始する．
  • 時刻 23: すぬけくんが座標 -26 で子供を捕まえたあと，正の方向へ移動を開始する．
  • 時刻 75: すぬけくんが座標 78 で子供を捕まえ，鬼ごっこが終了する．

入力例 2

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

出力例 2

937403116

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