Задача E. Плотность населения

Автор:Южно-Уральский открытый командный чемпионат   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

После проведения переписи населения Флатландии все данные были нанесены на карту. Прямоугольная карта Флатландии была разделена на клетки единичного размера. Число жителей в каждой клетке изменяется от 0 до 9.

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

Формат входного файла

В первой строке входного файла содержится три целых числа, разделенных пробелами — размеры Флатландии N, M и заданная плотность населения K. Далее следует N строк, каждая из которых содержит M цифр от 0 до 9 — карта распределения населения Флатландии.

Формат выходного файла

В первой строке выходного файла вывести четыре целых числа, разделяя их пробелами — номер строки и столбца для левого верхнего угла искомого прямоугольника, его высота и ширина. Если существует несколько областей максимальной площади, то вывести любой вариант. Если такой области не существует, вывести строку "0 0 0 0" (без кавычек).

Ограничения

1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ K ≤ 9

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 1
020
102
020
1 2 3 2

0.134s 0.013s 15