Вам дано клетчатое поле из n строк и n столбцов. Каждая клетка либо пуста (обозначается символом «.»), либо занята (обозначается символом «X»).
Две пустые клетки соединены напрямую, если у них есть общая сторона. Две клетки (r1, c1) (то есть клетка, расположенная в ряду r1 и столбце c1) и (r2, c2) соединены путём, если существует последовательность пустых клеток, начинающаяся с (r1, c1) и заканчивающаяся на (r2, c2), такая что любые две соседние клетки последовательности соединены напрямую. Компонентой связности называется множество пустых клеток, такое что любые две клетки множества соединены путём, и при этом никакая клетка множества не соединена путём ни с какой пустой клеткой не из этого множества.
Ваш друг Лимак — большой медведь гризли, способный разрушать препятствия в некоторой области. Точнее, вы можете попросить Лимака разрушить все препятствия в некотором квадрате k × k, то есть превратить все занятые клетки в свободные. Однако попросить помощи у Лимака можно только один раз.
Выбранный квадрат должен находиться строго внутри сетки. Возможно, что все клетки уже пусты и помощь Лимака вам никак не поможет.
Вы любите большие компоненты связности. Какую самую большую компоненту связности можно получить, попросив Лимака о помощи не более одного раза?
Примечание
В первом примере Лимак может сделать пустыми все клетки в каком-нибудь квадрате размером 2 × 2. Оптимальный способ выбрать квадрат показан красным на левом рисунке ниже. Таким образом, можно получить компоненту связности размером 10 клеток, отмеченную синим на правом рисунке ниже.
