D. Карта
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
128 megabytes
ввод
stdin
вывод
stdout

Задана карта местности, представляющая собой прямоугольную матрицу n × m, в каждой клетке которой записана средняя высота соответствующего участка местности. Прорабу Пете нужно расположить на карте несколько городов, каждый из которых на карте займет прямоугольник размера a × b клеток. Но прежде чем построить город в определенном месте, Пете необходимо убрать лишнюю землю с участка, на котором будет строиться город. Для этого он выбирает клетку наименьшей высоты на этом участке и делает высоту всех клеток на участке равной высоте этой клетки. Будем считать, что для того, чтобы опустить уровень земли с h2 до h1 (h1 ≤ h2), необходимо вывезти h2 - h1 единиц земли.

Назовем положение участка под город оптимальным, если количество вывозимой с него земли наименьшее из всех возможных положений. Петя строит города в соответствии со следующим алгоритмом: из всех оптимальных положений участка он выбирает самое верхнее. Если таких положений несколько, он выбирает среди них самое левое. На этом участке он строит город. Петя повторяет этот процесс до тех пор, пока он может построить хотя бы еще один город. На уже застроенных клетках, разумеется, строить вновь нельзя. Помогите Пете расположить города в соответствии с алгоритмом.

Входные данные

В первой строке перечислено через пробел четыре целых числа — размеры карты n, m и размеры города a, b (1 ≤ a ≤ n ≤ 1000, 1 ≤ b ≤ m ≤ 1000). Далее идут n строк по m неотрицательных целых чисел в каждой, задающие матрицу высот. Все числа не превышают 109. Числа в строках разделяются пробелами.

Выходные данные

В первой строке выведите k — число построенных городов. В следующих k строках выведите по 3 числа, разделенных пробелами, — номер строки и номер столбца левого верхнего угла очередного участка, а также объем земли, который требуется с него вывезти. Участки выводите в порядке их построения.

Примеры
Входные данные
2 2 1 2
1 2
3 5
Выходные данные
2
1 1 1
2 1 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