H. Hay Mower - 2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

仪表盘所有提交榜单题解

你可以在这里下载。

单点时限: 2.0 sec

内存限制: 256 MB

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.

T12_p1

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 \leq n, m \leq 500, 1 \leq k \leq 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 \leq a_{i, j} \leq 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 \leq x_{i} \leq n, 1 \leq y_{i} \leq m, 1 \leq t_{i} \leq 10^{18}$ hold for $1 \leq i \leq k$ and $t_{i}$ is strictly increasing.

输出格式

Output one integer indicating the answer modulo $998244353$ .

样例

Input

Output

Input

3 4 1
1 2 3 4
5 6 7 8
9 10 11 12
r 1 1000000000000000000

Output

172998509

提示

Sample $1$ :

At the end of moment $0$ , the farm looks like

$[\begin{matrix} 0 & 0 \\ 0 & 0 \end{matrix}]$

At the end of moment $5$ , Setsuna has cleared row $1$ and $15$ units of weed has been cut, so the farm looks like

$[\begin{matrix} 0 & 0 \\ 15 & 20 \end{matrix}]$

At the end of moment $6$ , Setsuna has cleared column $2$ and $26$ units of weed has been cut, so the farm looks like

$[\begin{matrix} 1 & 0 \\ 18 & 0 \end{matrix}]$

At the end of moment $7$ , Setsuna has cleared row $1$ and $4$ units of weed has been cut, so the farm looks like

$[\begin{matrix} 0 & 0 \\ 21 & 4 \end{matrix}]$

So the answer is $15 + 26 + 4 = 45$ units.

NaN

A. Archmage B. Bamboo Leaf Rhapsody C. Cheat Sheet D. Disaster Recovery E. Eight Digital Games F. Fake Algorithm G. Gentle Jena H. Hay Mower I. Immortal Trees J. JXC!! K. K-Shift L. Lottery Tickets M. MITE

比赛状态发生变化，点 OK 刷新。

OK

2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

输入格式

输出格式

样例

提示

题目列表

服务

开源

关于我们