Ледяной периметр
Фермер Джон собирается заняться производством мороженого! Он построил машину, которая производит капли мороженого, но, к сожалению, несколько неправильной формы. Фермер Джон надеется оптимизировать машину, чтобы на выходе получались более приемлемые формы.
Конфигурацию выхода мороженого автоматом можно описать с помощью сетки n × n следующим образом:
##.... ....#. .#..#. .##### ...### ....##
Каждый символ '.' представляет собой пустое пространство, а каждый символ '#' представляет квадратную ячейку 1 × 1 с мороженым.
К сожалению, в настоящий момент аппарат работает не очень хорошо и может производить несколько отсоединенных шариков мороженого (на рисунке выше их два). Шарик мороженого связан, если из любой его ячейки можно добраться до любой другой ячейки, совершая переходы по соседним ячейкам мороженого в северном, южном, восточном и западном направлениях.
Фермер Джон хотел бы найти площадь и периметр шарика мороженого, имеющего наибольшую площадь. Площадь шарика - это просто количество символов '#', являющихся его частью. Если несколько шариков обладают наибольшей площадью, то следует найти наименьший периметр среди них. На рисунке выше меньший шарик имеет площадь 2 и периметр 6, а больший шарик имеет площадь 13 и периметр 22.
Обратите внимание, что в центре шарика может быть "дыра" (пустое пространство, окруженное мороженым). В этом случае граница с отверстием также учитывается по периметру шарика. Шарики также могут быть вложенными в другие шарики, и в этом случае они рассматриваются как отдельные шарики. Например, в этом случае имеется шарик площадью 1, вложенный в шарик площади 16:
##### #...# #.#.# #...# #####
Знание площади и периметра шарика мороженого важно, поскольку фермер Джон в итоге хочет минимизировать отношение периметра к площади, величину, которую он называет ледяной изопериметрической мерой своего мороженого. Когда это соотношение мало, мороженое тает медленнее, так как у него меньшая площадь поверхности по сравнению с его массой.
Входные данные
Первая строка содержит число n (1 ≤ n ≤ 1000), а следующие n строк описывают выход машины. Конфигурация выхода мороженого содержит хотя бы один символ '#'.
Выходные данные
Выведите одну строку, содержащую два целых числа: площадь самого большого шарика мороженого и его периметр. Если существует несколько шариков с наибольшей площадью, то выведите информацию о том из них, у которого наименьший периметр.