Într-o cameră sunt aşezate n*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,..
, 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 de mai jos, sunt cel mult 8
acvarii vecine notate cu V1
, V2
, V3
,…, V8
). În cazul în care numărul peştilor vecini roşii este egal cu numărul peştilor vecini albaştrii, peştele studiat îşi va păstra culoarea.
Cerinţa
Scrieţi un program care să citească numerele naturale n
, m
, t
şi cele n*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 de intrare culori1.in
conține
- pe prima linie numerele naturale
n
,m
şit
, separate printr-un singur spaţiu, cu semnificaţia din enunț - pe următoarele
n
linii se află câtem
caracterer
saua
, pentru fiecare rând de acvarii, format astfel:- dacă peştele din acvariul cu numărul de ordine
i
(1≤i≤m
) din rândul curent este roşu, atunci cel de-ali
-lea caracter din linia fişierului de intrare, corespunzătoare rândului curent, ester
- dacă peştele din acvariul cu numărul de ordine
i
(1≤i≤m
) din rândul curent este albastru atunci cel de-ali
-lea caracter din linia fişierului de intrare, corespunzătoare rândului curent, estea
- dacă peştele din acvariul cu numărul de ordine
Date de ieșire
Fișierul de ieșire culori1.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 ≤ n < 50
,2 ≤ m < 50
,1 ≤ t ≤ 2300000
- Se garantează că există soluție pentru toate datele de test.
Exemplu 1
culori1.in
3 3 1 rar rra arr
culori1.out
rra rrr rrr
Exemplu 2
culori1.in
4 5 3 rrara aarra aarrr rrraa
culori1.out
aarrr aarrr rrrrr rrrrr