Фермер Джон собирается выпускать и продавать мороженое. Он построил
машину, которая производит шарики мороженого, но, к несчастью, немного
неправильной формы.
Конфигурация мороженого, которое производится машиной, может быть
описано решёткой \(N \times N\) grid (\(1 \leq N \leq 1000\)):
##....
....#.
.#..#.
.#####
...###
....##
Каждый символ '.' представляет пустое место, а каждый символ '#'
представляет \(1 \times 1\) квадратную ячейку мороженого.
К несчастью, сейчас машина работает не очень хорошо и может производить
несколько несвязанных сгустков мороженого (на картинке сверху их два).
Сгусток мороженого называется связным, если из любой ячейки сгустка можно
добраться до любой другой ячейки, перемещаясь в соседнюю по одному из
четырёх направлений (север, юг, запад, восток).
ФД хочет найти площадь и периметр сгустка, который имеет наибольшую
площадь. Площадь сгустка равна количеству символов '#' в его картинке.
Если несколько сгустков имеют одинаковую площадь, он хочет знать минимальный
периметр из них. На рисунке выше, маленький сгусток имеет площадь 2 и
периметр 6, а больший сгусток имеет площадь 13 и периметр 22.
Заметим, что сгусток может иметь "дыру" внутри (пустое пространство, окружённое мороженым). В таком случае граница "дыры" также учитывается в периметре
сгустка. Сгусток может находиться внутри другого сгустка, в этом случае они
рассматриваются как независимые сгустки. Например, ниже представлен сгусток
площади 1 внутри сгустка площади 16:
#####
#...#
#.#.#
#...#
#####
ФОРМАТ ВВОДА (файл perimeter.in):
Первая строка ввода содержит \(N\), а следующие \(N\) строк описывают вывод машины.
Присутствует, как минимум, один символ '#'.
ФОРМАТ ВЫВОДА (файл perimeter.out):
Выведите одну строку, содержащую два разделённых одиночным пробелом целых числа:
площадь наибольшего сгустка и его периметр. Если есть несколько сгустков
максимальной площади, вывести минимальный периметр.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
##....
....#.
.#..#.
.#####
...###
....##
|
13 22
|