AT_arc111_f.[ARC111F] Do you like query problems?

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 翻译