Are you tired of city life? Have you ever had illusions of pastoral peace? The clean atmosphere, the closeness to nature and the gentle pace of living, all made Setsuna yearn for the pastoral life more.
In order to experience the simple pastoral life, Setsuna has moved to Star Valley and started her farming journey.
Soon, she discovers the problem: overgrown weeds are harming her farm. In Chinese, we call it "Sheng Cao". She realized that weeding should be put at the top priority.
The farm can be described as an $n times m$ matrix. The growth rate of weed in row $i$ and column $j$ is denoted as $a_{i , j}$, indicating that the weed will grow $a_{i , j}$ units every *beginning* of the moment. At the end of moment $0$, there is no weed on the farm.
Setsuna will use mower $k$ times, where the $i$-th use occurs at the *end* of moment $t_i$. Each use of the mower completely removes weeds in a row or column.
Setsuna wonders how many units of weed she will remove.
The answer might be very large, so please output the desired answer modulo $998244353$.
The first line contains three integers $n, m, k (1 <= n, m <= 500, 1 <= k <= 3 times 10^5)$.
The next $n$ lines contains $m$ integers each, where the $j$-th integer of the $i$-th line is $a_{i , j} (0 <= a_{i , j} <= 10^(18))$.
The $i$-th of the next $k$ lines contains one character and two integers.
It is guaranteed that $1 <= x_i <= n, 1 <= y_i <= m, 1 <= t_i <= 10^(18)$ hold for $1 <= i <= k$ and $t_i$ is strictly increasing.
Output one integer indicating the answer modulo $998244353$.
Sample $1$:
At the end of moment $0$, the farm looks like
$$ \left[ \begin{matrix} 0 & 0 \\ 0 & 0 \\ \end{matrix} \right] $$
At the end of moment $5$, Setsuna has cleared row $1$ and $15$ units of weed has been cut, so the farm looks like
$$ \left[ \begin{matrix} 0 & 0 \\ 15 & 20 \\ \end{matrix} \right] $$
At the end of moment $6$, Setsuna has cleared column $2$ and $26$ units of weed has been cut, so the farm looks like
$$ \left[ \begin{matrix} 1 & 0 \\ 18 & 0 \\ \end{matrix} \right] $$
At the end of moment $7$, Setsuna has cleared row $1$ and $4$ units of weed has been cut, so the farm looks like
$$ \left[ \begin{matrix} 0 & 0 \\ 21 & 4 \\ \end{matrix} \right] $$
So the answer is $15 + 26 + 4 = 45$ units.
## Input
The first line contains three integers $n, m, k (1 <= n, m <= 500, 1 <= k <= 3 times 10^5)$.The next $n$ lines contains $m$ integers each, where the $j$-th integer of the $i$-th line is $a_{i , j} (0 <= a_{i , j} <= 10^(18))$.The $i$-th of the next $k$ lines contains one character and two integers. $"r"" "x_i " "t_i$ - Setsuna clears the weeds in row $x_i$ at the end of moment $t_i$. $"c"" "y_i " "t_i$ - Setsuna clears the weeds in column $y_i$ at the end of moment $t_i$. It is guaranteed that $1 <= x_i <= n, 1 <= y_i <= m, 1 <= t_i <= 10^(18)$ hold for $1 <= i <= k$ and $t_i$ is strictly increasing.
## Output
Output one integer indicating the answer modulo $998244353$.
[samples]
## Note
Sample $1$:At the end of moment $0$, the farm looks like$$ \left[ \begin{matrix} 0 & 0 \\ 0 & 0 \\ \end{matrix} \right] $$At the end of moment $5$, Setsuna has cleared row $1$ and $15$ units of weed has been cut, so the farm looks like$$ \left[ \begin{matrix} 0 & 0 \\ 15 & 20 \\ \end{matrix} \right] $$At the end of moment $6$, Setsuna has cleared column $2$ and $26$ units of weed has been cut, so the farm looks like$$ \left[ \begin{matrix} 1 & 0 \\ 18 & 0 \\ \end{matrix} \right] $$At the end of moment $7$, Setsuna has cleared row $1$ and $4$ units of weed has been cut, so the farm looks like$$ \left[ \begin{matrix} 0 & 0 \\ 21 & 4 \\ \end{matrix} \right] $$So the answer is $15 + 26 + 4 = 45$ units.
**Definitions**
Let $ n, m, k \in \mathbb{Z}^+ $ denote the dimensions of the farm and the number of mowing operations.
Let $ A = (a_{i,j}) \in \mathbb{Z}^{n \times m} $ be the growth rate matrix, where $ a_{i,j} $ is the growth rate of weeds at cell $ (i,j) $.
Let $ T = (t_1, t_2, \dots, t_k) $ be a strictly increasing sequence of mowing times, with $ t_i \in \mathbb{Z}^+ $ and $ t_1 \geq 1 $.
Let $ O = (o_1, o_2, \dots, o_k) $ be the sequence of operations, where each $ o_i \in \{ \text{row}, \text{col} \} \times \{1,\dots,n\} \times \{1,\dots,m\} $, specifying the type (row/column), index, and time $ t_i $ of the $ i $-th mowing.
**Constraints**
1. $ 1 \leq n, m \leq 500 $
2. $ 1 \leq k \leq 3 \times 10^5 $
3. $ 0 \leq a_{i,j} \leq 10^{18} $ for all $ i \in \{1,\dots,n\}, j \in \{1,\dots,m\} $
4. $ 1 \leq t_1 < t_2 < \dots < t_k \leq 10^{18} $
**Objective**
Compute the total weed mass removed over all $ k $ mowing operations, modulo $ 998244353 $.
Let $ R_i $ denote the total weed mass removed at the $ i $-th mowing.
If $ o_i $ is a row operation on row $ r $, then:
$$
R_i = \sum_{j=1}^m \left( a_{r,j} \cdot \left( t_i - t_{\text{last\_clear\_row}(r)} \right) \cdot \prod_{\substack{\ell < i \\ o_\ell \text{ is col} \\ \text{and col index } c}} \mathbf{1}_{c \text{ not cleared after last row } r \text{ clear}} \right)
$$
But more cleanly, define:
Let $ \text{last\_row}[r] $ be the last time row $ r $ was mowed before $ t_i $, or $ 0 $ if never.
Let $ \text{last\_col}[c] $ be the last time column $ c $ was mowed before $ t_i $, or $ 0 $ if never.
Then, the effective growth time for cell $ (i,j) $ before the $ i $-th mowing is:
$$
\tau_{i,j} = t_i - \max\left( \text{last\_row}[i], \text{last\_col}[j] \right)
$$
But since mowing clears entire row or column, and weeds grow continuously, the correct model is:
At any moment, the weed at $ (i,j) $ grows at rate $ a_{i,j} $.
When a row $ r $ is mowed at time $ t $, the weed removed from cell $ (r,j) $ is:
$$
a_{r,j} \cdot \left( t - \text{last\_clear}(r,j) \right)
$$
where $ \text{last\_clear}(r,j) = \max( \text{last\_row\_clear}[r], \text{last\_col\_clear}[j] ) $
Thus, define:
- Let $ r_{\text{last}}[i] $ be the last time row $ i $ was mowed (initially 0).
- Let $ c_{\text{last}}[j] $ be the last time column $ j $ was mowed (initially 0).
For each operation $ i $ at time $ t_i $:
- If it mows row $ r $:
$$
R_i = \sum_{j=1}^m a_{r,j} \cdot \left( t_i - \max(r_{\text{last}}[r], c_{\text{last}}[j]) \right)
$$
Then update $ r_{\text{last}}[r] = t_i $
- If it mows column $ c $:
$$
R_i = \sum_{i=1}^n a_{i,c} \cdot \left( t_i - \max(r_{\text{last}}[i], c_{\text{last}}[c]) \right)
$$
Then update $ c_{\text{last}}[c] = t_i $
**Total Answer:**
$$
\boxed{ \sum_{i=1}^k R_i \mod 998244353 }
$$