Стулья
"Принимая во внимание современные тенденции в области высоких технологий, с 2019 года Всероссийскую олимпиаду по информатике было решено проводить на планшетных компьютерах. Это нововведение настолько популяризовало программирование, что в 2020 году в отборочных этапах олимпиады приняло участие беспрецедентно много участников. Как следствие, количество участников заключительного этапа 2020 года также возросло, и в этом году впервые превысит порог в..."
Вот в такой сложной ситуации оказался оргкомитет заключительного этапа Всероссийской олимпиады по информатике 2020 года. Чтобы максимально комфортно разместить всех участников в зале, оргкомитет принял решение рассадить участников за квадратные столы, до четырех участников за каждый стол: ведь школьнику с планшетом много места для работы не нужно. У каждой стороны стола может стоять максимум один стул, иначе участники будут задевать друг друга локтями.
Всю ночь перед пробным туром отряд дежурных расставлял стулья вокруг столов по одним им известному принципу, и, как казалось, успешно справился с задачей, расставив необходимое количество стульев к утру. Но на пробном туре выяснились две новости, хорошая и плохая. Плохая новость — если два стула стоят спиной друг к другу, то дежурные не могут пройти между ними, поэтому в некоторые точки зала дежурные просто не могут попасть, что противоречит правилам проведения олимпиады. Хорошая новость — очень большой процент заявленных участников просто не доехал до места проведения и принимать участие в заключительном этапе не планирует, так что часть стульев можно просто убрать, и, таким образом, правила будут соблюдены.
Так что всю следующую ночь дежурные снова проведут в зале, теперь уже унося какие-то из лишних стульев, освобождая себе проход. Однако, есть опасность, что они увлекутся и вынесут что-нибудь не то, поэтому старший дежурный решил заранее нарисовать схему расстановки мебели, которой нужно добиться.
Схема должна отличаться от текущей расстановки мебели только отсутствием некоторых стульев. Мебель должна быть расставлена так, чтобы дежурные могли пройти в любую пустую точку зала, при этом из зала должно быть убрано как можно меньше стульев.
Входные данные
На вход подаются числа N и M — количество столов, помещающихся по ширине и по длине зала, а также план расстановки мебели в прямоугольном зале. Зал заполнен столами полностью, то есть столов всего N×M. План представляет собой таблицу размером 3N×3M, где каждый стол с его окружением задан квадратом 3×3.
В квадрате, задающим стол со стульями вокруг, стол обозначается латинской буквой T, стул — латинской буквой С, пустое место — символом ".". Гарантируется, что стол всегда стоит в центре такого квадрата. Стул может стоять только у одной из четырех сторон стола.
В первой строке через пробел вводятся числа N (1 ≤ N ≤ 100) и M (1 ≤ M ≤ 100). В следующих 3N строчках задается текущая расстановка мебели согласно указанному выше формату. Каждая строчка имеет длину 3M.
Выходные данные
Выведите план расстановки мебели в зале без лишних стульев в формате, аналогичному формату входных данных.