Единственное различие между простой и сложной версиями задачи состоит в том, что символ O не встречается во входных данных простой версии.
Errichto бросил Monogon-у следующий вызов, чтобы запугать его и не дать занять первое место по вкладу на Codeforces.
В таблице для игры в крестики нолики есть \(n\) строк и \(n\) столбцов. Каждая клетка таблицы либо пустая, либо содержит фишку. Всего есть два типа фишек: X и O. Если есть три фишки одного типа, последовательные в какой-то строке или в каком-то столбце, то это выигрышная конфигурация. Иначе это ничейная конфигурация.
Примеры в первой строке это выигрышные конфигурации. Примеры во второй строке это ничейные конфигурации. За одну операцию вы можете поменять фишку X на O или фишку O на X. Обозначим за \(k\) общее количество фишек в таблице. Ваша задача сделать таблицу ничейной за не более \(\lfloor \frac{k}{3}\rfloor\) (округление вниз) операций.
Вы не обязаны минимизировать количество операций.
Выходные данные
Для каждого набора входных данных выведите состояние таблицы после выполнения операций.
У нас есть доказательство, что решение всегда существует. Если есть несколько возможных решений, выведите любое.
Примечание
В первом наборе входных данных есть изначально три 'X' последовательных во второй строке и во втором столбце. Изменив фишку посередине на 'O' мы получим ничейную конфигурацию. При этом мы поменяли \(1\le \lfloor 5/3\rfloor\) фишку.
Во втором наборе входных данных мы изменяем \(9\le \lfloor 32/3\rfloor\) фишек и после этого не существует трех 'X' или 'O', последовательных в одной строке или одном столбце, поэтому это ничейная конфигурация.
В третьем наборе входных данных мы изменяем \(3\le \lfloor 12/3\rfloor\) фишки и получившаяся конфигурация будет ничейной.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
.X.
XXX
.X.
6
XX.XXX
XXXXXX
XXX.XX
XXXXXX
XX.X.X
XXXXXX
5
XXX.X
.X..X
XXX.X
..X..
..X..
|
.X.
XOX
.X.
XX.XXO
XOXXOX
OXX.XX
XOOXXO
XX.X.X
OXXOXX
XOX.X
.X..X
XXO.O
..X..
..X..
|