culori

Într-o cameră sunt aşezate $n \cdot m$ acvarii identice, pe $n$ rânduri, câte $m$ pe fiecare rând, unul lângă altul. În fiecare acvariu se află un singur peşte. Peştele poate fi de culoare roşie (culoare codificată cu $r$) sau albastră (codificată cu $a$). La fiecare moment de timp $t = 1,2,3,\dots$, peştii îşi modifică simultan culoarea astfel: fiecare peşte se colorează în culoarea pe care au avut-o la momentul $t-1$ majoritatea peştilor din acvariile învecinate (ca în desenul alăturat, sunt cel mult $8$ acvarii vecine notate cu $V_1,V_2,V_3,\dots,V_8$). În cazul în care numărul peştilor vecini roşii este egal cu numărul peştilor vecini albaştri, peştele studiat îşi va păstra culoarea.

Cerință

Scrieţi un program care să citească numerele naturale $n,m,t$ şi cele $n \cdot m$ coduri ale culorilor peştilor (cele de la momentul iniţial $t=0$) şi care să determine şi să afişeze codurile culorilor peştilor de la momentul $t$.

Date de intrare

Fișierul culori.in contine:

• pe prima linie numerele naturale $n \ m$ şi $t$, separate printr-un singur spaţiu, cu semnificaţia:
  • $n =$ numărul de rânduri pe care sunt aşezate acvariile
  • $m =$ numărul de coloane pe care sunt aşezate acvariile
  • $t =$ momentul de timp
• pe următoarele $n$ linii se află câte $m$ caractere $r$ sau $a$, pentru fiecare rând de acvarii, obţinute astfel:
  • dacă peştele din acvariul cu numărul de ordine $i$ din rândul curent este roşu, atunci cel de-al $i$-lea caracter din linia fişierului de intrare, corespunzătoare rândului curent, este r
  • dacă peştele din acvariul cu numărul de ordine $i$ din rândul curent este albastru atunci cel de-al $i$-lea caracter din linia fişierului de intrare, corespunzătoare rândului curent, este a

Date de ieșire

Fişierul de ieşire culori.out va conţine $n$ linii, fiecare linie va conţine câte $m$ caractere $r$ sau $a$, reprezentând codurile culorilor peştilor din rândul corespunzător numărului liniei curente din fişier

Restricții și precizări

• $2 \leq n \leq 50$
• $2 \leq m \leq 50$
• $1 \leq t \leq 2 \ 300 \ 000$

Exemplul 1

culori.in

3 3 1
rar
rra
arr

culori.out

rra
rrr
rrr

Explicație

Fişierul culori.in conţine $4$ linii. Sunt $9$ acvarii aşezate pe trei rânduri, câte trei acvarii pe fiecare rând. Peştii din primul rând au, în acestă ordine, culorile: roşu(r), albastru(a), roşu(r). Cei din al doilea rând au culorile: roşu(r), roşu(r), albastru(a), iar cei din al treilea rând: albastru(a) roşu(r), roşu(r). Culorile peştilor la momentul $t=1$ se modifică conform precizărilor din enunţ. Astfel pentru primul rând de acvarii, peştele din primul acvariu va avea culoarea roşie având $2$ vecini roşii şi $1$ vecin albastru; peştele din al doilea acvariu va avea culoarea roşie având $4$ vecini roşii şi $1$ albastru; peştele din al treilea acvariu va avea culoarea albastră având $1$ vecin roşu şi $2$ albaştri.

Exemplul 2

culori.in

4 5 3
rrara
aarra
aarrr
rrraa

culori.out

aarrr
aarrr
rrrrr
rrrrr

Explicație

Trasformările succesive ale culorilor peştilor sunt:

$t=1$

aarar
aarrr
arrra
arrrr

$t=2$

aaarr
aarrr
arrrr
rrrrr

$t=3$

aarrr
aarrr
rrrrr
rrrrr