题目描述

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$ 通りありますが、それらに対する出力のすべての和を $998{,}244{,}353$ で割った余りを求めてください。

求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $M$ $Q$

输出格式

答えを出力せよ。

题目大意

给出三个数 $n,m,q$。

你有一个长度为 $n$ 的序列 $a$，初始全为为 $0$，你有三种操作：
操作 $1$：给出 $l,r,v$，让区间 $[l,r]$ 对 $v$ 取 $\min$。
操作 $2$：给出 $l,r,v$，让区间 $[l,r]$ 对 $v$ 取 $\max$。
操作 $3$，给出 $l,r$，求区间和，将其累加进一个叫 $sum$ 的变量里。

你并不需要维护这个数据结构，而是统计一共有 $q$ 个操作的情况下，所有不同的操作序列中 $3$ 操作得到的 $sum$ 的总和，对 $998244353$ 取模。你需要保证 $v\in[0,m-1]$。

1 2 2

1

3 1 4

0

111 112 113

451848306

提示

制約

• $1\ \leq\ N,M,Q\ \leq\ 200000$
• 入力される数はすべて整数

Sample Explanation 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$ になるので、答えは $1$ です。