A29348.花火大会

时间限制：2000ms
内存限制：512MB

如夜空中绽放的花火，带走所有的忧愁与不快，任它们随风消散，只留下星辰般的宁静与温柔。

2024年8月24日，江户川区一年一度的「花火大会」如期举行。这次大会分布在江户川区的多个地点，同时在多个烟火发射点燃放烟花。每处烟花的燃放时间不一，烟花一旦点燃，便会向四周扩散，映照整片夜空。「花火大会」结束后，负责区域安全监测的你需要为主办方提供一份详细报告，报告中包括在江户川区每个地点看到烟花的最早时间。

给定一个 $N \times M$ 的地图，地图上的每个格子代表江户川区的一个区域。共有 $K$ 个地点布置了烟花，每个烟花 $i$ 的位置为 $(X_i, Y_i)$，并在 $Z_i$ 时燃放。每秒钟，烟花会沿上下左右四个方向无限散开（假设没有建筑物阻挡视线）。你的任务是计算在地图上每个区域看到烟花的最早时间。
由于这个输出可能会很大，所以我们采取以下方式输出答案。

令 $\tt{T_{i, j}}$ 表示 $(i, j)$ 处看到烟花的最早时间，输出答案为：

$$\tt{\sum_{i=1}^{N}\sum_{j=1}^{M} T_{i, j} \times 233^{i \times M + j} \mod{998244353}}$$

$\large{数据范围}$

• $1 \le N, M \le 5 \times 10^3$
• $1 \le K \le \min{\{1000, N \times M \}}$
• $1 \le X_i \le N$
• $1 \le Y_i \le M$
• $1 \le Z_i \le 10^9$
• $K$ 处地点互不相同。

对于每个测试文件格式如下：

$\tt{N\ M\ K}$
$\tt{X_1\ Y_1\ Z_1}$
$\tt{X_2\ Y_2\ Z_2}$
$\tt{\vdots}$
$\tt{X_K\ Y_K\ Z_K}$

对于每个测试文件，按照题目要求输出答案。

$\bf{样例\ 1：}$
在 $(1, 1)$ 处烟花在时间为 $1$ 时燃放，得出每个位置看到烟花的时间为：

$\tt{3\ 2\ 3}$
$\tt{2\ 1\ 2}$
$\tt{3\ 2\ 3}$

按照题目给出的方式计算答案应为 $793286413$。

$\bf{样例\ 2：}$
在 $(2, 6)$ 处烟花在时间为 $1$ 时燃放；
在 $(6, 3)$ 处烟花在时间为 $2$ 时燃放；
在 $(8, 8)$ 处烟花在时间为 $5$ 时燃放；
得出每个位置看到烟花的时间为：

$\tt{7\ 6\ 5\ 4\ 3\ 2\ 3\ 4\ 5}$
$\tt{6\ 5\ 4\ 3\ 2\ 1\ 2\ 3\ 4}$
$\tt{7\ 6\ 5\ 4\ 3\ 2\ 3\ 4\ 5}$
$\tt{6\ 5\ 4\ 5\ 4\ 3\ 4\ 5\ 6}$
$\tt{5\ 4\ 3\ 4\ 5\ 4\ 5\ 6\ 7}$
$\tt{4\ 3\ 2\ 3\ 4\ 5\ 6\ 7\ 8}$
$\tt{5\ 4\ 3\ 4\ 5\ 6\ 7\ 6\ 7}$
$\tt{6\ 5\ 4\ 5\ 6\ 7\ 6\ 5\ 6}$
$\tt{7\ 6\ 5\ 6\ 7\ 8\ 7\ 6\ 7}$

按照题目给出的方式计算答案应为 $61231456$。