Remote Training on Programming

Крестики-нолики на поле 3×3 клетки — хорошо знакомая любому человеку, и в особенности студенту, игра. Вам дано оцифрованное черно-белое изображение закончившейся игры. Требуется определить, кто же является победителем.

Задача осложняется тем, что поле может быть повернуто на любой угол. Кроме того, линии границ клеток оказались столь бледными, что при оцифровке изображения в черно-белый формат они исчезли.

Игра проходила согласно правилам — игроки ходят по очереди, первыми ходят крестики. Игра заканчивается в тот момент, когда один из участников выстроит 3 своих фигуры по горизонтали, вертикали или диагонали. Гарантируется, что игра закончилась победой одного из участников (варианта "ничья" быть не может).

Входные данные: первая строка содержит два разделенных пробелом целых числа — N (20 ≤ N ≤ 1000), M (20 ≤ M ≤ 1000) —  размеры рисунка по горизонтали и вертикали. В следующих M строках располагается изображение поля игры, каждая строка имеет длину N символов. Черные пиксели изображения представлены символом '*' (звездочка), белые — символом '.' (точка).

Гарантируется, что фигуры не соприкасаются — то есть любые два черных пикселя, являющиеся соседями по горизонтали, вертикали или диагонали, принадлежат одной фигуре. Кроме того, каждая фигура является связной — то есть от любого пикселя фигуры можно пройти до любого другого её пикселя, двигаясь по горизонтали, вертикали или диагонали по черным пикселям. Также известно, что внутри каждого "нолика", в отличие от “крестиков”, имеется одна непустая связная область белых пикселей, окруженная со всех сторон черными.

Рассматривая тестовый пример ниже, можно заметить, что фигуры не обязаны быть идентичны друг другу. Однако, крестик и нолик достаточно хорошо различимы, нолик напоминает собой эллипс, крестик напоминает два отрезка приблизительно одной длины, пересекающиеся около своих центров. Толщина линий фигур может быть более 1 пикселя. Никаких более четких характеристик фигур в данной задаче нет.

Выходные данные: выведите слово "crosses" в случае победы крестиков и слово "zeroes" в случае победы ноликов.

Примеры

Входные данные

Выходные данные

37 40 ..................................... ..................................... ..................................... ..................................... ...**.......*........................ ....*......**...******............... ....**....**....**...**.............. .....**.**......*.....*.............. ......***.......*.....**............. ......***.......*......*............. .....**.***.....*......*............. ....**....**....***...**............. ...**......**.....*****.............. ...*................................. ..............*.......*.............. ..............**.....**.............. .....*****.....**...**............... ....**...**.....**.**................ ....*.....*......***................. ...**.....*.....*****................ ....*.....*...***...**............... ....**...**...**.....*............... .....*****...**......**.............. .............*....................... ........................**.......*... .........................*......**... .........................**....*..... ..........................**.**...... ...........................***....... ...........................***....... .........................**..***..... ........................**.....***... ..................................... ..................................... ..................................... ..................................... ..................................... ..................................... ..................................... .....................................

crosses