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 の場合は鬼ごっこが終了となる.
- s の i 文字目が
-
すべての子供は,すぬけくんから遠ざかる方向へ常に速度 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
L
s and MR
s. 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.
- If the i-th character of s is
- 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