Do you like query problems?

AtCoder

IDarc111_f

Time4000ms

Memory256MB

Difficulty—

Yosupo loves query problems. He made the following problem: * * * > **A Query Problem** > We have an integer sequence of length $N$: $a_1,\ldots,a_N$. Initially, $a_i = 0 (1 \leq i \leq N)$. We also have a variable $ans$, which is initially $0$. Here, you will be given $Q$ queries of the following forms: > > * Type 1: > * $t_i (=1)$ $l_i$ $r_i$ $v_i$ > > * For each $j = l_i,\ldots,r_i$, $a_j := \min(a_j,v_i)$. > > * Type 2: > * $t_i (=2)$ $l_i$ $r_i$ $v_i$ > > * For each $j = l_i,\ldots,r_i$, $a_j := \max(a_j,v_i)$. > > * Type 3: > * $t_i (=3)$ $l_i$ $r_i$ > > * Compute $a_{l_i} + \ldots + a_{r_i}$ and add the result to $ans$. > > > Print the final value of $ans$. > Here, for each query, $1$ $\leq$ $l_i$ $\leq$ $r_i$ $\leq$ $N$ holds. Additionally, for Type 1 and 2, $0$ $\leq$ $v_i$ $\leq$ $M-1$ holds. * * * Maroon saw this problem, thought it was too easy, and came up with the following problem: * * * > **Query Problems** > Given are positive integers $N,M,Q$. There are $( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q$ valid inputs for "A Query Problem". Find the sum of outputs over all those inputs, modulo $998{,}244{,}353$. * * * Find it. ## Constraints * $1 \leq N,M,Q \leq 200000$ * All numbers in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $Q$ [samples]

Samples

Input #1

1 2 2

Output #1

1

There are $25$ valid inputs, and just one of them - shown below - results in a positive value of $ans$.
$t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1$
$ans$ will be $1$ in this case, so the answer is $1$.

Input #2

3 1 4

Output #2

Input #3

111 112 113

Output #3

451848306

API Response (JSON)

{
  "problem": {
    "name": "Do you like query problems?",
    "description": {
      "content": "Yosupo loves query problems. He made the following problem: * * * > **A Query Problem** > We have an integer sequence of length $N$: $a_1,\\ldots,a_N$. Initially, $a_i = 0 (1 \\leq i \\leq N)$. We also",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc111_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Yosupo loves query problems. He made the following problem:\n\n* * *\n\n> **A Query Problem**\n> We have an integer sequence of length $N$: $a_1,\\ldots,a_N$. Initially, $a_i = 0 (1 \\leq i \\leq N)$. We also...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments