At the World Robot Olympiad, robot golf competitions are held. The field where the game takes place is a rectangle consisting of $n \times m$ unit squares. The rows of the field are numbered from $1$ to $n$, and the columns from $1$ to $m$. Thus, each square is characterized by two positive integers $r$ and $c$ — the row and column numbers at whose intersection it is located.
Two robots take turns moving a special token across the field, where some squares contain traps. If the token is in square $(r, c)$, the robot whose turn it is can move it to square $(r + 1, c)$ or square $(r, c + 1)$. If the corresponding square does not exist because the token is in the last row or the last column of the field, the robot can move it off the field. The game ends when the token is either off the field or in a square with a trap.
Each trap corresponds to a certain integer $v_i$ — its value. The result of the game is equal to the value of the trap in which the game ended, or $0$ if the token ended up off the field. The robot that moves first aims to minimize the result of the game, and the robot that moves second aims to maximize it.
Let the token initially be in square $(r, c)$. The guaranteed result of the game $g(r, c)$ for this square is the minimum possible game result that the first-moving robot can achieve, regardless of the opponent's actions. Since the starting square is unknown before the match, the robot developers want to calculate the sum of the values $g(r, c)$ for all squares of the field.
You are required to write a program that, given the locations and values of the traps, determines the sum of the guaranteed game results for all squares of the field.
Input
The first line of the input contains three integers $n$, $m$, and $k$ ($1 \leqslant n, m \leqslant 10^9$; $1 \leqslant k \leqslant \min(n \cdot m, 10^5)$) — the number of rows, the number of columns, and the number of traps, respectively.
The next $k$ lines contain three integers $r_i$, $c_i$, and $v_i$ ($1 \leqslant r_i \leqslant n$, $1 \leqslant c_i \leqslant m$, $-10^9 \leqslant v_i \leqslant 10^9$) — the row number, column number, and the value of the $i$-th trap, respectively. No two traps are located in the same square.
Output
Output a single integer — the remainder of the sum of the guaranteed game results for all squares of the field divided by $998\,244\,353$.
The remainder of $a$ divided by $b$, where $a$ can be negative, is the number $r = a \pmod b$ lying in the range from $0$ to $b-1$, such that $a = qb + r$, where $q$ is an integer. For example, $13 \pmod 4 = 1$, $-13 \pmod 4 = 3$, $12 \pmod 4 = 0$, $-12 \pmod 4 = 0$.
Scoring
| Subtask | Points | Constraints | Dependencies |
|---|---|---|---|
| 1 | 20 | $n, m \leqslant 1000$ | - |
| 2 | 14 | $n \leqslant 5, m \leqslant 10^9$ | - |
| 3 | 14 | $n, m \leqslant 100\,000$, $k = n + m - 1$, for all $i$, $r_i = n$ or $c_i = m$ | - |
| 4 | 10 | For all $i$, $r_i \geqslant n - 1000$ and $c_i \geqslant m - 1000$ | 1 |
| 5 | 6 | $n, m \leqslant 100\,000$, for all $i$, $v_i = 1$ | - |
| 6 | 6 | For all $i$, $v_i = 1$ | 5 |
| 7 | 10 | $n, m \leqslant 100\,000$ | 1, 3, 5 |
| 8 | 10 | $k \leqslant 1000$ | - |
| 9 | 10 | - | 1–8 |
Examples
Input 1
3 3 3 2 3 -2 3 1 3 1 2 1
Output 1
998244352
Note
In the first example, the sum of the results is: $1 + 1 - 2 + 0 - 2 - 2 + 3 + 0 + 0 = -1$. The answer is $(-1) \pmod{998\,244\,353} = 998\,144\,352$.
Input 2
2 4 3 1 2 2 2 4 -3 2 1 1
Output 2
998244348
Note
In the second example, the sum of the results is: $1 + 2 + 0 - 3 + 1 + 0 - 3 - 3 = -5$. The answer is $(-5) \pmod{998\,244\,353} = 998\,244\,348$.