Let's Play Tag

AtCoder

IDarc129_f

Time8000ms

Memory256MB

Difficulty—

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 $M$ `R`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$. * 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$ [samples]

Samples

Input #1

3 3
1 2 3
1 2 3

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.

Input #2

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

Output #2

937403116

API Response (JSON)

{
  "problem": {
    "name": "Let's Play Tag",
    "description": {
      "content": "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 ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc129_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Snuke and $N+M$ children are standing on a number line.\nAt time $0$, they are at the following positions.\n\n*   Snuke is at coordinate $0$.\n*   $N$ children are at negative coordinates. The $i$\\-th of ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments