Lai cīnītos pret automašīnu zādzībām, speciālistu grupa ir izstrādājusi slepenas ierīces pirmo versiju. Ierīce tiek uzstādīta uz automašīnas un raida datus tikai par tās kustības virzienu.

Pilsētas karte ir taisnstūrveida rūtiņu laukums, kur katra rūtiņa atbilst vai nu vietai, kur drīkst braukt (tās kartē tiek apzīmētas ar '.'), vai arī vietai kur braukt nav iespējams (tās kartē tiek apzīmētas ar 'X'). Automašīnas sākotnējā atrašānās vieta kartē ir apzīmēta ar zvaigznīti ('*'). Automašīna var vairākkārt braukt cauri savai sākotnējai atrašanās vietai.

Automašīna katrā brīdī var braukt vienā no četriem virzieniem: uz ziemeļiem (uz augšu), uz dienvidiem (uz leju), uz austrumiem (pa labi), uz rietumiem (pa kreisi).

Automašīnas kustība tiek uzdota kā kustības virzienu virkne. Katrā no minētajiem virzieniem automašīna ir veikusi vismaz vienu rūtiņu.

Uzrakstiet programmu, kas dotai pilsētas kartei, automašīnas sākotnējās atrašanās vietai un kustības virzienu virknei atrod visas iespējamās tās atrašanās vietas kustības beigās!

Ievaddatu pirmajā rindā dotas divu naturālu skaitļu R(pilsētas kartes rindu skaits, 1≤R≤50) un C(pilsētas kartes kolonu skaits, 1≤C≤50) vērtības, kas atdalītas ar tukšumsimbolu.

Katrā no nākošajām R faila rindām dots pa C simboliem ('.','X' vai '*') katrā. Faila i+1-ā rinda atbilst kartes i-tajai rindai.

Faila nākošajā rindā dota naturāla skaitļa N(kustības virzienu virknes garums, 1≤N≤1000) vērtība.

Katrā no nākošajām N faila rindām dots pa vienam vārdam katrā. Šis vārds var būt NORTH, SOUTH, WEST vai EAST, kas nozīmē, ka konkrētajā brīdī automašīna ir braukusi, attiecīgi, uz ziemeļiem, dienvidiem, rietumiem vai austrumiem. Virzieni ir doti tieši tādā secībā kā automašīna ir braukusi. Divi pēc kārtas doti virzieni savā starpā ir atšķirīgi! 

Izvaddatiem jāsatur tieši R rindas pa C simboliem katrā. Tai jāatspoguļo pilsētas karte ar '*' tikai tajās vietās, kur kustības beigās var atrasties automobilis.

Uzdevums izmantots Horvātijas informātikas olimpiādē 2001.gadā