Рабочее место участника

Город 4е сильно вырос и было решено разделить его на 4 района. Город имеет форму квадрата размером `N\ times\ N` кварталов. Каждый квартал либо застроен зданием, либо является пустым. Для разделения на районы нужно провести две прямые линии между кварталами – по вертикали и горизонтали – таким образом, чтобы количества зданий в каждом районе не слишком сильно отличались.

Напишите программу, которая по плану города вычислит способ разделения города на 4 района, минимизирующий значение выражения `∑(K_i-K/4)^2`, где `K` – количество зданий в городе, `K_i` – количество зданий в `i`-м районе. Если существует несколько вариантов с минимальным значением, то вывести из них тот вариант, в котором минимально значение выражения `∑(S_i-S/4)^2`, где `S\ =\ N^2` – общая площадь города, `S_i` – площадь `i`-го района. При одинаковых значениях обоих выражений выбрать минимальное значение для положения горизонтальной границы, затем – вертикальной.

Во входном файле несколько тестовых случаев. Каждый тест начинается со строки, содержащей одно целое число `N` (`2\ ≤\ N\ ≤\ 500`) – размер города. Далее следует `N` строк, содержащих по `N` символов – план города. Символ '#' означает квартал со зданием, символ '.' – пустырь. Набор тестов заканчивается строкой, содержащей число 0.

Для каждого тестового случая вывести строку, содержащую два целых числа, разделенных пробелом – положение вертикальной, затем горизонтальной линий разделения города на районы. Верхний левый угол имеет координаты (0,0), правый нижний – `(N,N)`.

4
####
#...
.#..
..#.
3
#.#
.#.
#.#
0

2 1
1 1