← 返回题目列表

AtCoder · arc111_f

F. 你喜欢查询问题吗?

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

Yosupo 喜欢查询问题。他提出了如下问题:


一个查询问题

我们有一个长度为的整数序列 N: a_1,\ldots,a_N。最初, a_i = 0 (1 \leq i \leq N)。 我们还有一个变量 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看到这个问题,觉得太简单了,于是想出了下面的问题:


查询问题

给定的是正整数 N,M,Q。有 ( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q “查询问题”的有效输入。求所有这些输入的输出总和,模数 998{,}244{,}353.


找到它。

约束

  • 1 \leq N,M,Q \leq 200000
  • 输入的所有数字均为整数。

输入

输入由标准输入按以下格式给出:

N M Q

输出

打印答案。


样本输入 1

1 2 2

示例输出 1

1

有 25 有效输入,并且只有其中一个 - 如下所示 - 会产生正值 ans.

t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1

ans 将是 1 在这种情况下,所以答案是 AtCoder 线沿线的 1.


示例输入 2

3 1 4

示例输出 2

0

示例输入 3

111 112 113

示例输出 3

451848306