Три друга любят играть в следующую игру. Первый друг выбирает строку \(S\). Затем второй друг создает новую строку \(T\), который состоит из двух копий строки \(S\). Наконец, третий друг вставляет одну букву в начале, в конце или где-то внутри строки \(T\), тем самым создавая новую строку \(U\).

Дана строка \(U\), ваша задача – восстановить исходную строку \(S\).

Долгое время на острове Байтопия правил справедливый король Байтазар. Но после внезапной смерти царя двое его сыновей-близнецов Битеон и Байтеон не смогли прийти к соглашению, кто из них должен взойти на трон. Поэтому они решили разделить остров на две провинции, чтобы управлять ими самостоятельно. На прямоугольной карте Байтопия имеет форму многоугольника из N вершин.

Каждая сторона многоугольника параллельна одной из сторон карты, а любые две соседние стороны перпендикулярны друг другу. Ни одна из сторон многоугольника не пересекает и не касается любой другой стороны, за исключением общей вершины двух последовательных сторон.

Битеон и Байтеон хотят разделить многоугольник на два конгруэнтных многоугольника, используя один отрезок, содержащийся в полигоне и параллельный одной из сторон карты. (Два многоугольника называются конгруэнтными, если один может быть совмещён с другим с помощью комбинации отражений, поворотов и параллельных переносов). Координаты вершин многоугольника и точки разделяющего отрезка – целые числа.

Сыновья короля просили Вас проверить, возможно ли провести такое разделение.

По данной форме острова, определите, может ли он быть разделен горизонтальным или вертикальным отрезком на две конгруэнтные части. Если это возможно, найдите любой такой отрезок.