时间限制： 2.0 秒 3.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$ 行）表示棋盘上水滴的分布情况。由上至下，由左至右输出，每行三个正整数表示行号、列号、水滴数。

4 4 12 1
1 2 1
1 3 2
2 1 1
2 4 1
3 1 1
3 4 1
4 2 1
4 3 1
2 2 4
2 3 4
3 2 4
3 3 3
2 2

4
1 2 3
1 3 4
2 1 3
2 4 2
3 1 3
3 4 2
4 2 2
4 3 2

样例 1 解释

整个过程从上到下、从左到右表示。

字母表示该格子即将发射水滴的方向（U：上, D：下, L：左, 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 可以直接使用常数更小的做法。
• 在同时间复杂度的做法中选取使用时间和空间常数均更小的做法。