AT_arc111_f [ARC111F] Do you like query problems?

[problemUrl]: https://atcoder.jp/contests/arc111/tasks/arc111_f yosupo 君非常喜欢查询类问题，因此他设计了如下的问题。 ------ > **A Query Problem** > > 有一个长度为 $N$ 的整数序列 $a_1,\ldots,a_N$。初始时，$a_i=0\ (1\leq i\leq N)$。另外，还有一个变量 $ans$，初始时 $ans=0$。接下来会有 $Q$ 个如下形式的查询： > > - 查询 1： > > - $t_i (=1)\ l_i\ r_i\ v_i$ > - 对于每个 $j=l_i,\ldots,r_i$，执行 $a_j := \min(a_j, v_i)$ > - 查询 2： > > - $t_i (=2)\ l_i\ r_i\ v_i$ > - 对于每个 $j=l_i,\ldots,r_i$，执行 $a_j := \max(a_j, v_i)$ > - 查询 3： > > - $t_i (=3)\ l_i\ r_i$ > - 计算 $a_{l_i}+\ldots+a_{r_i}$，并将其加到 $ans$ 上 > > 请输出最终的 $ans$ 的值。 > > 其中，对于每个查询，$1\leq l_i\leq r_i\leq N$，并且对于查询 1、2，有 $0\leq v_i\leq M-1$。 ------ maroon 君觉得这个问题太简单了，于是又提出了如下的问题。 ------ > **Query Problems** > > 给定正整数 $N, M, Q$。对于问题 “A Query Problem”，其输入共有 $(\frac{(N+1)N}{2}\cdot(M+M+1))^Q$ 种可能。请计算所有这些输入对应的输出 $ans$ 的和，并对 $998,244,353$ 取模。 ------ 请你求出答案。

输入从标准输入中给出。 > $N\ M\ Q$

请输出答案。

### 数据范围 - $1\leq N, M, Q\leq 200000$ - 输入的所有数均为整数 ### 样例解释 1 所有可能的输入共有 $25$ 种，其中 $ans$ 会大于 $0$ 的输入只有一种：$t_1=2,\ l_1=1,\ r_1=1,\ v_1=1,\ t_2=3,\ l_2=1,\ r_2=1$。此时 $ans=1$，所以答案为 $1$。 由 ChatGPT 4.1 翻译