{"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 have a variable $ans$, which is initially $0$. Here, you will be given $Q$ queries of the following forms:\n> \n> *   Type 1:\n>     *   $t_i (=1)$ $l_i$ $r_i$ $v_i$\n>         \n>     *   For each $j = l_i,\\ldots,r_i$, $a_j := \\min(a_j,v_i)$.\n>         \n> *   Type 2:\n>     *   $t_i (=2)$ $l_i$ $r_i$ $v_i$\n>         \n>     *   For each $j = l_i,\\ldots,r_i$, $a_j := \\max(a_j,v_i)$.\n>         \n> *   Type 3:\n>     *   $t_i (=3)$ $l_i$ $r_i$\n>         \n>     *   Compute $a_{l_i} + \\ldots + a_{r_i}$ and add the result to $ans$.\n>         \n> \n> Print the final value of $ans$.\n> 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.\n\n* * *\n\nMaroon saw this problem, thought it was too easy, and came up with the following problem:\n\n* * *\n\n> **Query Problems**\n> 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$.\n\n* * *\n\nFind it.\n\n## Constraints\n\n*   $1 \\leq N,M,Q \\leq 200000$\n*   All numbers in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc111_f","tags":[],"sample_group":[["1 2 2","1\n\nThere are $25$ valid inputs, and just one of them - shown below - results in a positive value of $ans$.\n$t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1$\n$ans$ will be $1$ in this case, so the answer is $1$."],["3 1 4","0"],["111 112 113","451848306"]],"created_at":"2026-03-03 11:01:14"}}