配点 : $1000$ 点

問題文

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)$
• $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)$
• $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$ に足す
• $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$ で割った余りを求めてください。

---

求めてください。

制約

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

入力

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

$N$ $M$ $Q$

出力

答えを出力せよ。

1 2 2

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$ です。

3 1 4

0

111 112 113

451848306