SPOJ in Armenian

Ինֆորմատիկայի օլիմպիադայի եզրափակիչ փուլի անցկացման ժամանակ կազակերպիչները որոշեցին մասնակիցներին նստեցնել քառակուսի սեղանների շուրջն այնպես, որ յուրաքանչյուր սեղանի շուրջ լինի ամենաշատը 4 մասնակից: Աշակերտներից  յուրաքանչյուրին տրվում է մեկ լափթոփ: Սեղանի յուրաքանչյուր կողմում թույլատրվում է դնել ամենաշատը մեկ աթոռ:

Փորձնական փուլից առաջ կազմակերպիչները բոլոր սեղանների շուրջը տեղադրեցին անհրաժեշտ քանակության աթոռներ: Սակայն փորձնական փուլում պարզվեց, որ երբ երկու աթոռներ դրված են միմյանց նկատմամբ թիկունքով, ապա արդեն այդ երկու աթոռների միջև տարածություն չի լինում, և հսկիչների համար անհնար է դառնում անցնել դրանց միջով: Հետևաբար դահլիճում լինում են տեղեր, որտեղ հսկիչները չեն կարող հասնել: Սա հակասում է օլիմպիադայի անցկացման կանոններին:

Բայց փորձնական փուլին պարզվեց, որ եզրափակիչ փուլ անցած մասնակիցների զգալի մասը չի ներկայացել օլիմպիադային, այնպես որ աթոռների մի մասը կարելի է հեռացնել դահլիճից այնպես, որ օլիմպիադայի անցկացման կանոնները չխախտվեն:

Խնդիրը հետևյալն է՝ պետք է հեռացնել նվազագույն քանակության աթոռներ այնպես, որ հսկիչները կարողանան անցնել դահլիճի յուրաքանչյուր ազատ կետ:

Մուտք

Ներմուծվում են երկու թվեր՝ N և M, որոնք ցույց են տալիս դահլիճի լայնությամբ և երկարությամբ տեղադրված սեղանների քանակը: Դահլիճն ամբողջությամբ լցված է սեղաններով, այսինքն դրանց ընդհանուր քանակը N × M է: Կահույքի տեղաբաշխման պլանն ունի 3N × 3M չափի աղյուսակի տեսք, որտեղ յուրաքանչյուր սեղան իր շրջակայքով ներկայացված է 3 × 3 չափի քառակուսով: Քառակուսիներից յուրաքանչյուրում սեղանը ներկայացվում է T տառով, աթոռը՝ C, իսկ ազատ տեղը՝ “.”: Երաշխավորվում է, որ սեղանը միշտ քառակուսու կենտրոնում է, իսկ աթոռը կարող է դրվել սեղանի չորս կողմերից մեկում:

Առաջին տողում տրված են N (1 ≤ N ≤ 100) և M (1 ≤ M ≤ 100) թվերը: Հաջորդ 3N տողերում տրված է կահույքի ընթացիկ դասավորությունը վերը նշված ձևաչափով: Յուրաքանչյուր տող ունի 3M երկարություն:  

Արտածել դահլիճում կահույքի դասավորման պլանը (վերը նշված ձևաչափով) ավելորդ աթոռները հեռացնելուց հետո:

Օրինակներ.

Մուտք.

2 2
......
.TCCT.
.C..C.
.C..C.
.TCCT.
......

Ելք.

......
.T.CT.
.C..C.
.C..C.
.TCCT.
......

Մուտք.

1 1
.C.
CTC
.C.

Ելք.

.C.
CTC
.C.