1. Tabuľa a fixka vzorové riešenie

Peťka má bielu tabuľu. Peťka tiež má červenú fixku, ktorou práve po tabuli čmárala. Lenže niekedy počas toho čmárania fixka vyschla. Suchá fixka nielen že nepísala, ale dokonca z tabule mazala už nakreslené čiary.

V tejto úlohe si predstavíme, že tabuľa je jedna veľká obdĺžniková bitmapa s \(r\) riadkami a \(s\) stĺpcami. Jednotlivé políčka bitmapy budeme volať pixely. Na začiatku sú všetky pixely tabule biele. Kým fixka píše, farbí dotknuté pixely na červeno. Keď už fixka vyschla, odfarbuje dotknuté pixely späť na bielo.

Peťka začne kresliť v čase 0, kedy zoberie do ruky fixku. V čase 1 sa fixkou dotkne políčka v ľavom dolnom rohu bitmapy. Od tejto chvíle môžeme Peťkino kreslenie popísať ako postupnosť akcií. Popis každej akcie má tvar “smer kroky”. Údaj smer je jeden zo štyroch možných reťazcov: up, down, left alebo right. Údaj kroky je kladné celé číslo: počet krokov daným smerom, ktoré Peťka spraví. Každý krok predstavuje pohyb fixky o 1 pixel v danom smere. Každý krok trvá jednotkový čas.

Ak by napríklad prvá akcia bola “up 3”, pohla by Peťka postupne fixku o 3 pixely dohora. Nových pixelov tabule by sa fixka dotkla postupne v časoch 2, 3 a 4.

Úloha

Na vstupe sú dané rozmery tabule a zoznam Peťkinych akcií. Na vstupe je tiež daná jedna konkrétna bitmapa tvorená červenými a bielymi pixelmi.

Zistite, či daná bitmapa môže byť výsledkom Peťkinho čmárania. Ak áno, nájdite najmenšiu aj najväčšiu hodnotu \(t\) takú, že je možné, že fixka vyschla niekedy medzi časmi \(t\) a \(t+1\).

(Najmenšia platná hodnota \(t\) je nula. Táto hodnota znamená, že fixka vyschla skôr ako sa ňou Peťka prvýkrát dotkla tabule. Najväčšia platná hodnota \(t\) je rovná času kedy Peťka dokončila poslednú akciu. Táto hodnota znamená, že fixka vyschla až po tom ako Peťka dokreslila.)

Formát vstupu

V prvom riadku vstupu sú tri celé čísla: rozmery tabule \(r\) a \(s\) a počet akcií \(n\).

Nasleduje \(r\) riadkov a v každom z nich \(s\) znakov: bitmapa, ktorú chceme nakresliť. Znak # (mriežka) predstavuje červený pixel, znak . (bodka) biely.

Každý z posledných \(n\) riadkov vstupu obsahuje popis jednej Peťkinej akcie, a to v poradí, v akom ich vykonala.

Obmedzenia

• \(1\leq r,c\)
• \(r\cdot c \leq 1\,000\,000\) (čiže dokopy je nanajvýš milión pixelov)
• \(1\leq n\leq 1\,000\,000\)
• počet krokov v každej akcii je kladný
• popis akcií má tú vlastnosť, že Peťka počas kreslenia nikdy neopustí plochu tabule
• z vyššie uvedených obmedzení sa dá odvodiť obmedzenie na maximálny možný celkový čas kreslenia
• je päť testovacích sád: prvá je rozumne malá, druhá je rozumne krátka a zvyšok je škaredší :)

Formát výstupu

Vypíšte jeden riadok v tvare “\(t_1\) \(t_2\)”, kde \(t_1\) je najmenší a \(t_2\) najväčší spomedzi časov, po ktorých mohla vyschnúť fixka tak, aby sme dostali zadaný obrázok. Ak sa zadaný obrázok nedá vyrobiť, vypíšte “\(-1\) \(-1\)”.

Príklady

Input:

6 8 5
........
...#....
########
#..#...#
#..#####
#.......
up 3
right 7
down 2
left 4
up 3

Output:

20 20

Fixka musela celý čas písať.

Input:

6 8 5
........
........
###.####
#......#
#..#####
#.......
up 3
right 7
down 2
left 4
up 3

Output:

17 17

Fixka musela vyschnúť medzi časmi 17 a 18. Viď obrázok.

Input:

3 3 2
...
.#.
...
up 2
right 2

Output:

-1 -1

Stredný pixel nemá ako byť červený, fixka tadiaľ nikdy nešla.

Input:

2 2 4
..
..
up 1
right 1
down 1
left 1

Output:

0 1

Jedna možnosť je, že fixka bola celý čas suchá. Je tu však aj iná možnosť: fixka mohla v čase 1 ešte písať, ale v čase 5 sme si to už suchou fixkou zmazali.