ŽUPANIJSKO NATJECANJE 2013. / Srednja škola, II. podskupina (3. i 4. razred) - 2. zadatak

U dalekoj budućnosti na novotkrivenom planetu nekoliko izvanzemaljskih rasa pokušava zauzeti što više vrijednih resursa.

Svaka rasa, u trenutku slijetanja na planet, odabire slobodnu lokaciju i na nju spušta svoju baznu letjelicu.

Iz letjelice izlaze kolonizatori koji postepeno pokušavaju zauzeti sav okolni teritorij, osim područja koja su prekrivena otrovima drevne civiclizacije koja je davno zagadila svoj okoliš i izumrla, zbog čega niti jedna rasa ne može zauzeti ova područja.

Planet je prikazan pravokutnom pločom podijeljenom na N*M kvadratnih teritorija organiziranih u N redaka i M stupaca.

Susjedi nekog teritorija su oni teritoriji neposredno gore, dolje, lijevo i desno od njega (ako postoje).

Za svaku rasu poznat je korak Ti u kojem će ona sletiti na planet.

U svakom koraku X kolonizatori će se iz ranije zauzetih teritorija pokušati proširiti na sve susjedne teritorije prema sljedećim pravilima:

• ako je neka druga rasa zauzela susjedni teritorij u ranijem trenutku, tada nije moguće da ga bilo koja rasa preuzme

• ako je susjedni teritorij slobodan (nije ga zauzela niti jedna rasa i nije zagađen), ali ga druga rasa (ili rase) također pokušava(ju) zauzeti u istom trenutku, dolazi do sukoba:

  • u sukobu prevladava rasa koja je u svim prethodnim koracima zauzela najveći broj teritorija. U slučaju izjednačenja između dvije ili više rasa, teritorij postaje trajno prekriven otrovima i niti jedna ga rasa više ne može zauzeti

• ako je susjedni teritorij slobodan i samo ga jedna rasa pokušava u određenom trenutku zauzeti, ta ga rasa uspješno zauzima.

Nakon što je zauzimanje u koraku X završeno, sleću sve rase za koje je Ti jednak X te time korak X završava.

Svi kolonizatori zauzimaju područja istovremeno, a uspjeh osvajanja teritorija na kojima dolazi do sukoba ovisi isključivo o teritorijima zauzetim u ranijim koracima kolonizacije.

Nakon kratkog razmišljanja shvaćate da, ako su vam poznati početni izgled planeta te vremena i lokacije spuštanja svake rase na planet, možete odrediti izgled planeta u bilo kojem trenutku.

Napišite program koji će iscrtati izgled planeta nakon koraka K.

Ulazni podaci

U prvom redu ulaza nalaze se prirodni brojevi N i M (1 ≤ N, M ≤ 100), broj redaka i stupaca pravokutne ploče kojom prikazujemo izgled planeta.

U drugom retku ulaza nalaze se dva broja: R i K (1 ≤ R ≤ 26, 1 ≤ K ≤ 1 000 000), broj rasa koje stižu na planet i broj koraka koje je potrebno predvidjeti.

U sljedećih N redaka prikazan je početni izgled planeta.

U svakom retku nalazi se po M znakova koji prikazuju izgled odgovarajućeg teritorija: znak '.' (točka) predstavlja slobodan teritorij, dok znak '$' (dolar) predstavlja zagađen teritorij.

U sljedećih R redaka nalaze se po tri broja: Ti, Xi, Yi (1 ≤ Ti ≤ K, 1 ≤ Xi ≤ N, 1 ≤ Yi ≤ M), koji opisuju korak, redak i stupac teritorija na koji sljeće i-ta rasa.

Rasa će uvijek sletjeti na teritorij koji je slobodan, nezagađen i niti jedna rasa ne pokušava ga zauzeti u Ti - tom koraku.

Izlazni podaci

Potrebno je ispisati N redaka od kojih se svaki sastoji od M znakova: izgled planeta nakon K koraka.

Slobodna i zagađena polja u ispisu trebaju biti označena znakovima “.” i “$”, a polja koja je zauzela i-ta rasa označena su i-tim malim slovom engleske abecede (1. rasa slovom „a‟,

1. rasa slovom „c‟, a 8. rasa slovom „h‟).

Primjeri test podataka

Ulaz

5 5
1 2
.....
.....
.....
.....
.....
1 3 3

Izlaz

.....
..a..
.aaa.
..a..
.....

Ulaz

5 5
2 4
.....
.....
.$...
....$
.....
2 2 3
3 4 4

Izlaz

.aaa.
aaaaa
.$aa.
..ab$
...b.

Ulaz

9 11
3 8
...........
...........
...........
...........
...........
...........
.....$.....
...........
...........
1 1 1
1 1 11
5 6 6

Izlaz

aaaaa$bbbbb
aaaaa$bbbbb
aaaaa$bbbbb
aaaaacbbbbb
aaaacccbbbb
aaacccccbbb
aa.cc$cc.bb
a...c.c...b
...........