P13789 「CZOI-R6」游戏

有一片 $n\times m$ 的空地，CaiZi 定好了两个常数 $k_1, k_2$，决定在这片空地进行 $q$ 局游戏。 每局游戏内，CaiZi 会先选择空地内某点 $(x_i, y_i)$，设定一个基准得分 $u_i$。随后，对于空地内所有点 $(a, b)\;(1 \leq a \leq n, 1 \leq b \leq m)$，其在该局游戏的得分为 $u_i + k_1 \cdot \lvert x_i - a \rvert + k_2 \cdot \lvert y_i - b\rvert$。 作为观战方，你想要对每个位置 $(i, j) (1 \leq i \leq n, 1 \leq j \leq m)$ 求出其在 $q$ 局游戏中得分的 **最大值**。 **注意 $\boldsymbol{k_1, k_2}$ 未必为正数，详见各子任务约束范围**。

第一行 $5$ 个整数，依次为 $n,m,q,k_1,k_2$。 接下来 $q$ 行，第 $i$ 行 $3$ 个整数，依次为 $x_i,y_i,u_i$。

令位置 $(i, j)$ 在所有游戏中得分的最大值为 $f_{i,j}$。 为了减少输出量，你仅需要输出一行一个整数 $$ \left(\sum_{i=1}^n \sum_{j=1}^m f_{i,j} \cdot 131^{(i-1) \times m+j} \right) \bmod{2^{64}} $$ 即可。如果你使用 C++ 语言，`unsigned long long` 类型的自然溢出能够自动达到对 $2^{64}$ 取模的效果。 **保证正解不依赖于此输出方式，即能够独立求出所有 $\boldsymbol{f_{i,j}}$ 的值**。

**【样例解释】** 对于第一组数据，加密前各个位置的得分最大值依次为 $$ \begin{bmatrix} 6 &5 &4 \\ 5 &4 &4 \\ 4 &4 &5 \end{bmatrix}. $$ 对于第二组数据，加密前各个位置的得分最大值依次为 $$ \begin{bmatrix} 8 &11 &8 &5 &2 \\ 6 &9 &6 &3 &3 \\ 4 &7 &4 &5 &5 \\ 6 &9 &6 &7 &7 \end{bmatrix}. $$ --- **【数据范围】** - Subtask #1（$10\ \text{pts}$）：$n, m, q \le 100$。 - Subtask #2（$20\ \text{pts}$）：$k_1=0$。 - Subtask #3（$20\ \text{pts}$）：$n,m\le10^3$，$k_1,k_2 < 0$。 - Subtask #4（$20\ \text{pts}$）：$q$ 局游戏的 $u_i$ 相同。 - Subtask #5（$30\ \text{pts}$）：无特殊限制。 对于 $100\%$ 的数据，$1\le x_i\le n\le3\times10^3$，$1\le y_i\le m\le3\times10^3$，$1\le q\le10^6$，$|k_1|,|k_2|,|u_i|\le10^9$。