Background

Translated from ROI 2019 D2T3.

In the "Robot Olympic Games", there is a "Robot Golf" contest. The course is a rectangle made of $n \times m$ unit squares. Rows are numbered from $1$ to $n$, and columns are numbered from $1$ to $m$. Each unit square is represented by two positive integers $r$ and $c$, which are its row and column indices.

Two robots take turns moving a special "golf ball" on the course, and some squares may contain holes. If the "golf ball" is on square $(r, c)$, the robot whose turn it is can move it to square $(r + 1, c)$ or square $(r, c + 1)$. If the "golf ball" is in the last row or the last column, the robot may move it outside the boundary of the course. The game ends in one of two cases: the "golf ball" goes outside the boundary, or the "golf ball" falls into a hole.

Each hole corresponds to an integer $v_i$, which is its value. The game result equals the value of the hole where the "golf ball" ends up; if the "golf ball" goes outside the boundary, the result is $0$. The first robot aims to minimize the game result, and the second robot aims to maximize the game result.

Problem Description

Let $g(r, c)$ denote the minimum possible game result that the first robot can guarantee, no matter how the opponent plays, when the "golf ball" initially starts at square $(r, c)$. Since the initial square is unknown before the contest starts, the robot developers want to compute the sum of $g(r, c)$ over all squares, i.e. $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}g(i,j)$.

Input Format

The first line contains three integers $n,m,k$, representing the number of rows, the number of columns, and the number of holes.

The next $k$ lines each contain three integers $r_i,c_i,v_i$, representing the row index, column index, and value of a hole. No two holes are located on the same square.

Output Format

Output one integer, equal to $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}g(i,j)\bmod998244353$. Note: the output should be between $0$ and $998244352$, not between $-998244352$ and $998244352$.

3 3 3
2 3 -2
3 1 3
1 2 1

998244352

2 4 3
1 2 2
2 4 -3
2 1 1

998244348

Hint

Sample Explanation:

In the first sample, $g(r,c)$ for all squares is as follows (the gray squares contain holes):

The total sum is: $1 + 1 - 2 + 0 - 2 - 2 + 3 + 0 + 0 = -1$. The answer is $(-1) \bmod 998 244 353 = (-1 + 998 244 353) = 998 244 352$.

In the second sample, $g(r,c)$ for all squares is as follows:

The total sum is: $1 + 2 + 0 - 3 + 1 + 0 - 3 - 3 = -5$. The answer is $(-5) \bmod 998 244 353 = 998 244 348$.

Constraints:

Special Property A: For every $i$, $r_i=n$ or $c_i=m$.

Special Property B: For every $i$, $r_i\ge n-1000$ and $c_i\ge m-1000$.

Special Property C: For every $i$, $v_i=1$.

For $100\%$ of the testdata, $1\le n,m\le10^9,1\le k\le\min(n\times m,10^5),1\le r_i\le n,1\le c_i\le m,|v_i|\le10^9$.

Translated by ChatGPT 5