Problem Statement

Yosupo loves query problems. He made the following problem:

A Query Problem
We have an integer sequence of length N: $a_1,\ldots,a_N. Initially, a_i = 0 (1 \leq i \leq N)$.
We also have a variable ans, which is initially 0.
Here, you will be given Q queries of the following forms:

• Type 1:

• t_i (=1) l_i r_i v_i

• For each $j = l_i,\ldots,r_i, a_j$ :$= \min(a_j,v_i)$.

• Type 2:

• t_i (=2) l_i r_i v_i

• For each $j = l_i,\ldots,r_i, a_j$ :$= \max(a_j,v_i)$.

• Type 3:

• t_i (=3) l_i r_i

• Compute $a_{l_i} + \ldots + a_{r_i}$ and add the result to ans.

Print the final value of ans.
Here, for each query, $1 \leq l_i \leq r_i \leq N$ holds. Additionally, for Type 1 and $2, 0 \leq v_i \leq M-1$ holds.

Maroon saw this problem, thought it was too easy, and came up with the following problem:

Query Problems
Given are positive integers N,M,Q. There are $( \frac{(N+1)N}{2} \cdot (M+M+1) )^Q$ valid inputs for "A Query Problem". Find the sum of outputs over all those inputs, modulo 998{,}244{,}353.

Find it.

Input

Input is given from Standard Input in the following format:
N M Q

Output

Print the answer.

Constraints

• $1 \leq N,M,Q \leq 200000$
• All numbers in input are integers.

Sample Input 1

1 2 2

Sample Output 1

1

There are 25 valid inputs, and just one of them - shown below - results in a positive value of ans.
t_1 = 2, l_1 = 1, r_1 = 1, v_1 = 1, t_2 = 3, l_2 = 1, r_2 = 1
ans will be 1 in this case, so the answer is 1.

Sample Input 2

3 1 4

Sample Output 2

0

Sample Input 3

111 112 113

Sample Output 3

451848306

见题面 Input 部分

见题面 Output 部分