На шашечной доске размером N × N клеток расположены несколько белых и несколько черных шашек.
Горизонтали доски обозначены числами 1, 2, 3, … снизу вверх. (То есть первая строка входных данных описывает горизонталь доски с номером N, вторая N − 1 и т.д.)
Вертикали обозначены буквами a, b, c, … слева направо.
Клетка, таким образом, задается комбинацией из буквы и числа, например d12.
Ход шашки задается перечислением всех клеток, которые она посетила за этот ход,
включая начальную и конечную.
Обозначения клеток при этом разделяются знаком - (минус). Например: a1-c3-e1.
Шашка может побить (взять) шашку противоположного цвета,
"перепрыгнув" через нее по диагонали в любом направлении.
Если после этого имеется возможность взять еще одну шашку, то это можно сделать на том же ходу.
Требуется определить ход черных, соответствующий наиболее длинному взятию.
Если имеется несколько вариантов хода, выдать любой из них.
Формат входного файла
В первой строке входного файла содержится число N.
В следующих N строках — описание позиции, состоящее из символов '.' (точка),
'O' (заглавная латинская О),'X' (заглавная латинская X).
Они определяют пустую клетку, белую шашку и черную шашку соответственно.
Формат выходного файла
В выходном файле должна содержаться единственная строка вида
L1N1 − L2N2 − … − LKNK, где K ≥ 1,
или Impossible если взятие невозможно.
Прямоугольная рамка была разрезана на N кусков.
Каждый кусок может представлять собой либо отрезок прямой, либо "уголок" — два отрезка,
соединённых под прямым углом.
По данным длинам отрезков требуется восстановить исходную рамку или определить,
что это невозможно.
Куски можно поворачивать, но нельзя отражать. Требуется использовать все куски.
Формат входного файла
Входной файл содержит число кусков N, за которым следуют N пар целых чисел aibi,
описывающих длину двух отрезков "уголка" i-го куска.
Если кусок является отрезком, то ai = 0 либо bi = 0.
Формат выходного файла
Выходной файл должен содержать два положительных целых числа WH —
ширину и высоту рамки, при этом W ≥ H.
Если решения не существует, следует выдать число − 1.
Если решений несколько, следует выдать решение с максимальным значением W.
