Глеб играет в градостроительный симулятор «SteamCity».
Он решил построить город в прямоугольнике, состоящем из $$$n \times m$$$ клеток. Чтобы усложнить себе задачу, Глеб будет строить этот город в пустыне...
Чтобы жители города не страдали от жажды, было решено обеспечить им доступ к воде. Для этого Глеб будет использовать колодцы. К сожалению, каждый колодец занимает целую клетку прямоугольника, зато у всех граничащих по стороне или по диагонали клеток будет доступ к воде. Итого, колодцы нужно расставить так, чтобы у каждой клетки (не занятой колодцем) был доступ к воде. Кроме того, Глебу не чужда эстетика. Он хочет построить колодцы так, чтобы их расположение было симметрично, как по вертикали, так и по горизонтали.
Например, такие расположения колодцев являются симметричными (колодцы обозначены голубым цветом):
примеры корректного расположения
А такие — нет (в первом случае нет симметрии по вертикали, во втором — по горизонтали, в третьем — обеих):
примеры некорректного расположения
Глеб хочет построить как можно меньше колодцев, соблюдая описанные условия. Помогите ему — предложите вариант расположения колодцев, при котором выполнены все условия, а количество колодцев минимально.
В первой строке заданы два натуральных числа — $$$n$$$ и $$$m$$$, $$$1 \leq n, m \leq 100$$$.
Выведите $$$n$$$ строк по $$$m$$$ символов в каждой — расположение колодцев в городе. Символ 'O' (заглавная латинская буква) должен соответствовать колодцу, символ '+' — клетке без колодца. Если существует несколько оптимальных решений, можно вывести любое из них.
| Группа | Баллы | Доп. ограничения | Комментарий |
| $$$0$$$ | $$$0$$$ | — | Тесты из условия |
| $$$1$$$ | $$$50$$$ | $$$n, m \leq 8$$$ | Каждый тест |
| $$$2$$$ | $$$50$$$ | — | Каждый тест |
3 4
++++ O++O ++++
Легко видеть, что в предложенном в примере расположении двух колодцев у каждой клетки есть доступ к воде. Существуют и другие варианты расположения двух колодцев при соблюдении всех условий. Однако, одним колодцем обойтись не получится.
