| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 27 | 0 | 0 | 0.000% |
Фермер Архип решил заняться земледелием и выращивать брюссельскую редиску. Для этого он купил прямоугольное поле, состоящее из n рядов по m участков в каждом. Все участки являются одинаковыми и имеют квадратную форму. Оказалось, что на момент покупки некоторые из этих участков уже удобрены, а некоторые — нет. Редиска растет только на удобренных участках.
Для получения большего урожая Архип решил удобрить некоторый прямоугольный фрагмент поля, состоящий из целых участков. В выбранном фрагменте Архип удобряет каждый участок. Повторное удобрение участка делает его непригодным к выращиванию брюссельской редиски. Закончив удобрять, фермер выбирает для посадки редиски прямоугольный фрагмент поля, состоящий из целых участков, каждый из которых удобрен ровно один раз.
Архип должен выбрать на поле фрагмент для удобрения таким образом, чтобы фрагмент для посадки редиски имел максимальную площадь. Напишите программу, которая по заданному полю находит фрагмент поля для удобрения и фрагмент поля под посадку.
В первой строке входного файла записаны натуральные числа n и m (2 ≤ n ≤ 2000, 2 ≤ m ≤ 2000), где n — количество рядов на поле, а m — количество участков в каждом ряду (количество столбцов). Далее в n строках содержится описание поля. Каждая из этих n строк содержит m символов. Символ «1» обозначает, что соответствующий участок поля удобрен, а «0» — не удобрен. Гарантируется, что поле содержит хотя бы один удобренный и хотя бы один неудобренный участок. Поле расположено таким образом, что первая строка его описания соответствует северной стороне, а первый столбец — западной стороне.
Первая строка должна описывать фрагмент поля для удобрения. Фрагмент описывается четырьмя числами a, b, c, d, где a и b — номер ряда и столбца самого северо-западного его участка, а c и d — номер ряда и столбца самого юго-восточного. Ряды нумеруются с севера на юг от 1 до n, а столбцы — с запада на восток от 1 до m.
Вторая строка должна описывать фрагмент под посадку в том же формате.
Третья строка должна содержать площадь фрагмента (количество участков) под посадку.
Если решений несколько, выведите любое.
4 6 111110 110010 111100 000000
2 3 2 5 1 1 3 4 12