Zadanie

Krásny obdĺžnik

Počet bodov: 70, časový limit: 1000ms

Paulinka si jedného dňa našla krásny štvorfarebný obdĺžnik a položila si ho na policu. Keď prišla po prázdninách späť na internát, uvedomila si, že už sa jej nezdá dostatočne krásny. Rozhodla sa ho trochu prefarbiť.

Úloha

Obdĺžnik je rovnomerne rozdelený na štvorčeky, má \(r\) riadkov a \(s\) stĺpcov. Každý štvorček je buď Azúrový, Brontofúzikový, Cyklaménový alebo Dúhový. Paulinke sa páči rozmanitosť a preto by chcela aby každý štvorček 2x2 obsahoval každú farbu práve raz. Zistite koľko najmenej farieb musí prefarbiť tak, aby bol obdĺžnik krásny (spĺňal horeuvedenú podmienku) a jeden takýto obdĺžnik vypíšte.

Vstup a výstup

Na vstupe dostanete v prvom riadku čísla \(r\) a \(s\). Na ďalších \(r\) riadkoch je string \(s\) znakov pozostávajúcich z ABCD – popis obdĺžnika.

\(r, s \geq 2\) a \(r\times s \leq 300\,000\)

Vypíšte \(r\) riadkov po \(s\) znakov – ako má obdĺžnik vyzerať.

Príklady

Input:

2 2
AB
CD

Output:

AB
CD

Tu netreba nič meniť. Obdĺžnik je pekný aj na začiatku.

Input:

3 5
ABCAB
ABCAB
ABCAB

Output:

DBCAD
CADBC
DBCAD

Tento obdĺžnik nebol veľmi pekný. Museli sme prefarbiť až 9 štvorčekov.