U419470 水滴

**时间限制：** 2.0 秒 **空间限制：** 512 MB

这是一个经典的游戏。 在一个 $n\times m$ 的棋盘上，每一个格子中都有一些水滴。玩家的操作是，在一个格子中加一滴水。 当一个格子中的水滴数超过了 $4$，这一大滴水就会因格子承载不住而向外扩散。扩散的规则是这样的 : 这个格子中的水滴会消失，然后分别向上、左、下、右， $4$ 个方向发射一个水滴。如果水滴碰到一个有水的格子，就会进入这个格子。否则水滴会继续移动直到到达棋盘边界后消失。扩散后，水滴进入新的格子可能导致该格子的水滴数也超过 $4$，则会立即引发这个格子的扩散。我们规定，每个格子按逆时针顺序从上方向开始，递归处理完每一个方向的扩散以及其引发的连锁反应 ，再处理下一个方向的扩散。 给定棋盘的初始状态和玩家的操作，求最后水滴的分布情况。 由于把水滴在一个空格看起来用处不大，所以保证所有的玩家操作都不会选择空格。 提示：可以记录每个水滴上下左右方向第一个水滴的位置，扩散时根据规则模拟，并在每次操作后维护。

从标准输入读入数据。 第一行四个整数 $n,m,c,T$。 接下来 $c$ 行，每行三个正整数 $x_i,y_i,a_i$，表示初始棋盘上第 $x_i$ 行 $y_i$ 列有 $a_i$ 个水滴。 接下来 $T$ 行，每行两个正整数 $u_i,v_i$，表示在第 $u_i$ 行 $v_i$ 列放入一个水滴。

输出到标准输出。 输出 $T$ 加若干行。 前 $T$ 行每行一个整数，第 $i$ 行表示在第 $i$ 次操作后扩散的水滴数。若没有扩散输出 $0$。 最后若干行（可能是 $0$ 行）表示棋盘上水滴的分布情况。由上至下，由左至右输出，每行三个正整数表示行号、列号、水滴数。

### 样例 1 解释   整个过程从上到下、从左到右表示。 字母表示该格子即将发射水滴的方向( $\texttt{U}$：上, $\texttt{D}$：下, $\texttt{L}$：左, $\texttt{R}$：右 )。 黄色格子表示即将发射水滴的格子。 ### 子任务 对于所有数据，保证： - $1\le n,m\le 351493,~1\le c \le 750000,~1\le T\le 500000$； - $1\le x_i,u_i\le n,~1\le y_i,v_i\le m,~1\le a_i\le 4$； - 初始棋盘的水滴没有重复的 $(x_i,y_i)$，玩家操作过程中 $(u_i,v_i)$ 处一定有水滴。 **本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。** - 子任务 1（17 分）：保证 $n,m\le 100$。 - 子任务 2（24 分）：保证 $n,m\le 2000$。 - 子任务 3（24 分）：保证 $c\le 10^5$。 - 子任务 4（35 分）：无特殊性质。 ### 提示 **由于数据规模较大，输入输出规模可达上百万个整数，请务必使用快速的方式进行输入输出。** 此外，请使用一些方法尽可能优化时间常数，包括但不限于： - 在递归模拟的过程中尽可能修改全局数组和全局变量，递归函数返回类型设为 `void`，减少堆栈消耗空间； - 对数据范围分治，不同子任务使用不同的解法，例如对于子任务 1 和 2 可以直接使用常数更小的做法。 - 在同时间复杂度的做法中选取使用时间和空间常数均更小的做法。