题目描述 这是一个经典的游戏。 在一个 $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$。这里一次扩散指一个格子因水滴数超过 $4$ 而整体消失并向四个方向发射水滴，计数按发生扩散的格子次数统计。 最后若干行（可能是 $0$ 行）表示棋盘上水滴的分布情况。由上至下、由左至右输出，每行三个正整数，表示行号、列号和水滴数。 数据范围 对于所有数据，保证： $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 分）：无特殊性质。 输入样例1 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 输出样例1 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 样例说明 整个过程从上到下、从左到右表示。字母表示该格子即将发射水滴的方向，其中 U 表示上，D 表示下，L 表示左，R 表示右；黄色格子表示即将发射水滴的格子。