Map

题意翻译

### 题目描述 给你一个 $n\times m$ 的矩形,你需要从中依次选出若干个 $a\times b$ 矩形直至无法再选择,依次选择的矩形满足以下条件: 1. 此矩形不能和之前的矩形重叠。 1. 这个矩形在所有可选矩形中的花费最小。一个矩形的花费为:此矩形的权值和 $-$ 此矩形最小权值 $\times $ 矩形大小。 1. 如果有多个花费最小的矩形,则优先选行坐标最小的,其次选列坐标最小的。 ### 输入格式 第一行四个正整数 $n,m,a,b$。 接下来 $n$ 行,每行 $m$ 个正整数。 ### 输出格式 第一行一个整数 $q$ 表示一共有 $q$ 个矩形依次被选择。 接下来 $q$ 行,每行三个整数 $x_i,y_i,w_i$ 。表示选择的第 $i$ 个矩形左上角的行列坐标,以及该矩形的花费。

题目描述

There is an area map that is a rectangular matrix $ n×m $ , each cell of the matrix contains the average height of a corresponding area part. Peter works for a company that has to build several cities within this area, each of the cities will occupy a rectangle $ a×b $ cells on the map. To start construction works in a particular place Peter needs to remove excess ground from the construction site where a new city will be built. To do so he chooses a cell of the minimum height within this site, and removes excess ground from other cells of the site down to this minimum level. Let's consider that to lower the ground level from $ h_{2} $ to $ h_{1} $ ( $ h_{1}<=h_{2} $ ) they need to remove $ h_{2}-h_{1} $ ground units. Let's call a site's position optimal, if the amount of the ground removed from this site is minimal compared to other possible positions. Peter constructs cities according to the following algorithm: from all the optimum site's positions he chooses the uppermost one. If this position is not unique, he chooses the leftmost one. Then he builds a city on this site. Peter repeats this process untill he can build at least one more city. For sure, he cannot carry out construction works on the occupied cells. Would you, please, help Peter place cities according to the algorithm?

输入输出格式

输入格式


The first line contains four space-separated integers: map sizes $ n $ , $ m $ and city sizes $ a $ , $ b $ ( $ 1<=a<=n<=1000 $ , $ 1<=b<=m<=1000 $ ). Then there follow $ n $ lines, each contains $ m $ non-negative space-separated numbers, describing the height matrix. Each number doesn't exceed $ 10^{9} $ .

输出格式


In the first line output $ k $ — the amount of constructed cities. In each of the following $ k $ lines output 3 space-separated numbers — the row number and the column number of the upper-left corner of a subsequent construction site, and the amount of the ground to remove from it. Output the sites in the order of their building up.

输入输出样例

输入样例 #1

2 2 1 2
1 2
3 5

输出样例 #1

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

输出样例 #2

3
3 1 2
3 3 3
1 2 9