Chairs#5775
textitIn response to the latest trends in high technology, since 2019, the All-Russian Olympiad in Informatics ("Всероссийская олимпиада по информатике") has been conducted using tablet computers. This innovation greatly increased the popularity of programming, leading to a record number of participants in the 2020 qualifying rounds. Consequently, the number of participants in the 2020 final stage has also risen, and for the first time, it will surpass the threshold of...
This situation presents a challenge for the organizing committee of the final stage of the All-Russian Olympiad in Informatics ("Всероссийская олимпиада по информатике") 2020. To ensure all participants are comfortably seated, the committee decided to use square tables, accommodating up to four participants per table. Since each participant uses a tablet, minimal workspace is required. Each side of a table can have at most one chair to prevent participants from bumping elbows.
The night before the trial round, a team of attendants arranged chairs around the tables according to their own method, seemingly completing the setup by morning. However, during the trial round, two issues arose: one positive and one negative. The negative news was that if two chairs are placed back-to-back, attendants cannot pass between them, blocking access to certain areas of the hall, which violates Olympiad rules. The positive news was that a significant number of registered participants did not show up and do not plan to attend the final stage, allowing for some chairs to be removed to meet the rules.
Thus, the attendants will spend the following night in the hall, removing some of the extra chairs to create clear paths. However, there is a risk they might remove more than necessary, so the head attendant decided to prepare a furniture arrangement plan in advance to be achieved.
The plan should only differ from the current setup by the removal of some chairs. The furniture must be arranged so that attendants can access any empty spot in the hall, while removing the fewest possible chairs.
The input consists of numbers and — representing the number of tables that fit across the width and length of the hall, along with the current furniture arrangement plan in the rectangular hall. The hall is completely filled with tables, totaling N \times M tables. The plan is depicted as a grid of size 3N \times 3M, where each table and its surroundings are represented by a 3 \times 3 square.
In this square, the table is marked by the letter T, a chair by the letter C, and an empty space by the symbol ".". The table is always located at the center of the square. A chair can only be placed on one of the four sides of the table.
The first line provides the numbers (1 \leq N \leq 100) and (1 \leq M \leq 100), separated by a space. The following lines describe the current furniture arrangement as per the format outlined above. Each line has a length of .
Output the revised furniture arrangement plan for the hall, eliminating excess chairs, in a format similar to the input data format.
Example 1