B. 地图（Map）

题目描述

有一张 n × m 的矩形地图，每个格子中存放着对应区域的平均海拔高度。Peter 的公司需要在这片区域上建造若干座城市，每座城市将占据地图上的一个 a × b 矩形地块。

在一个位置开工前，需要先移走多余的土方：施工方会选择该地块内高度最小的格子，然后把地块内其他格子的高度都降低到这个最小高度。若把某个格子的高度从 h₂ 降到 h₁（h₁ ≤ h₂），需要移走 h₂ − h₁ 单位的土。

若一个候选位置的花费在所有候选位置中最小，则称该位置是最优的。Peter 按以下算法建造城市：

1. 从所有最优位置中，选择最靠上（行号最小）的；若仍不唯一，选择最靠左（列号最小）的。
2. 在该位置建造城市，被该城市占用的格子不能再次施工。
3. 重复以上过程，直到无法再建造任何一座城市。

请你帮助 Peter 输出城市的建造顺序。

输入格式

第一行包含 4 个整数：地图大小 n, m 与城市大小 a, b（1 ≤ a ≤ n ≤ 1000，1 ≤ b ≤ m ≤ 1000）。

接下来 n 行，每行 m 个非负整数，表示海拔高度矩阵，每个数不超过 10⁹。

输出格式

第一行输出一个整数 k——建造的城市数量。

接下来 k 行，每行输出 3 个整数——该城市的左上角格子所在的行号、列号，以及需要移走的土方量。按建造顺序输出。

样例

样例 1

输入：

2 2 1 2
1 2
3 5

输出：

2
1 1 1
2 1 2

样例 2

输入：

4 4 2 2
1 5 3 4
2 7 6 1
1 1 2 2
2 2 1 2

输出：

3
3 1 2
3 3 3
1 2 9

数据范围与子任务

• 对于 100% 的数据：1 ≤ a ≤ n ≤ 1000，1 ≤ b ≤ m ≤ 1000，0 ≤ hᵢⱼ ≤ 10⁹。