Два медведя играют в крестики-нолики по переписке. Медведям давно надоели обычные крестики-нолики на доске три на три, поэтому они играют в чуть более сложную версию этой игры. Опишем её правила.
Игра происходит на следующем поле:
Игроки ходят по очереди. На первом ходу первый игрок может поставить свою фишку в любую клетку любого маленького поля. Далее на ходы накладываются ограничения — если на предыдущем ходу оппонент поставил свою фишку в клетку с координатами (xl, yl) в некотором маленьком поле, то свой текущий ход игрок обязан совершить в маленькое поле с координатами (xl, yl). Например, если первый игрок своим ходом поставит свою фишку в нижнюю левую клетку центрального поля, то второй игрок обязан своим ходом поставить свою фишку в нижнее левое поле (обратите внимание на первый тестовый пример). Если в поле, в которое игрок должен ставить фишку, нет свободных клеток, то он может сделать ход в любую свободную клетку любого поля.
Вам дано текущее поле игры, а также координаты клетки, в которую был сделан последний ход. Вам необходимо определить, в какие клетки может поставить свою фишку текущий игрок.
Почтальоном в лесу работает заяц и он любит пакостить медведям. Поэтому он иногда немного перерисовывает игровое поле, но делает это так, чтобы медведи не заметили. А именно: в клетке, в которую был сделан последний ход, обязательно стоит фишка одного из игроков. Поэтому текущая позиция может быть недостижимой. Вам не нужно выяснять, достижима текущая позиция или нет, просто выведите возможные ходы следующего игрока.
В первых 11 строках вам задана таблица 9 на 9, которая пробелами и переводами строк разбита на 9 маленьких полей, внутри каждого из которых описано соответствующее поле без пробелов и переводов строк. Символ «x» (ASCII-код 120) обозначает, что соответствующая клетка занята фишками первого игрока, «o» (ASCII-код 111) — фишками второго, символ «.» (ASCII-код 46) обозначает пустую клетку.
После таблицы в единственной строке записаны два целых числа x и y (1 ≤ x, y ≤ 9) — координаты клетки, в которую был сделан последний ход. Строки в таблице нумеруются сверху вниз, а столбцы — слева направо. Гарантируется, что в клетке, в которую был совершен последний ход находится либо символ «x», либо символ «o».
Также гарантируется, что существует хотя бы одна свободная клетка. Не гарантируется, что данная позиция достижима.
Выведите поле в аналогичном формате, где все клетки, в которые может поставить свою фишку очередной игрок заменены на «!» (ASCII-код 33). Все остальные клетки должны остаться без изменений.
... ... ...
... ... ...
... ... ...
... ... ...
... ... ...
... x.. ...
... ... ...
... ... ...
... ... ...
6 4
... ... ...
... ... ...
... ... ...
... ... ...
... ... ...
... x.. ...
!!! ... ...
!!! ... ...
!!! ... ...
xoo x.. x..
ooo ... ...
ooo ... ...
x.. x.. x..
... ... ...
... ... ...
x.. x.. x..
... ... ...
... ... ...
7 4
xoo x!! x!!
ooo !!! !!!
ooo !!! !!!
x!! x!! x!!
!!! !!! !!!
!!! !!! !!!
x!! x!! x!!
!!! !!! !!!
!!! !!! !!!
o.. ... ...
... ... ...
... ... ...
... xxx ...
... xox ...
... ooo ...
... ... ...
... ... ...
... ... ...
5 5
o!! !!! !!!
!!! !!! !!!
!!! !!! !!!
!!! xxx !!!
!!! xox !!!
!!! ooo !!!
!!! !!! !!!
!!! !!! !!!
!!! !!! !!!
Разберём первый тестовый пример.
В нём первый игрок сделал свой первый ход в нижнюю левую клетку центрального поля, поэтому второй игрок может ставить свою фишку только в нижнее левое поле.
Во втором тесте последний ход был сделан в верхнюю левую клетку нижнего центрального поля, однако все клетки в верхнем левом поле уже заняты, поэтому второй игрок может ставить свою фишку в любую свободную клетку любого поля.
В третьем тесте последний ход был сделан в центральную клетку центрального поля, однако все клетки там уже заняты, поэтому первый игрок может ставить фишку в любую свободную клетку любого поля. Обратите внимание, что такая позиция недостижима.
