U419470 水滴

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

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

无

无

### 样例 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 分）：无特殊性质。 **由于数据规模较大，输入输出规模可达上百万个整数，请务必使用快速的方式进行输入输出。**