题目描述

有一片 $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}}$ 的值。

3 3 3 1 1
1 1 1
3 2 1
3 3 2

1817640486886175503

4 5 3 2 -3
3 2 7
1 5 1
2 4 3

15847710135880645119

提示

【样例解释】

对于第一组数据，加密前各个位置的得分最大值依次为

$$\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$。