3. Zaujímavé kŕmenie strašidelnej príšery

Kým ste prázdninovali, kúpali sa, plávali, KSPáci svedomito pracovali. Kolektívne spisovali príklady, ktorými sa po konci slnečných prázdnin potrápite. Samozrejme, príklady sa spravili počas prvých pár piatkov. Krátko potom prišla prázdnota.

“Kam sa počneme po spravení príkladov?” premýšľali.

“Pôjdeme sa kúpať? Prechádzať sa po kopcoch? Spoznávať krásy sveta? Programovať? Kŕmiť pestrofarebné papagáje poletujúce po parku?”

“Kdeže, kúpime si príšeru!” prehlásil Peter. Každý súhlasil.

Po kúpe príšery prišli prvé problémy. Príšeru potrebovali pravidelne kŕmiť. Samozrejme, potrebovali pre príšeru pekné priestory. Príšera potrebuje pohodlie. Posledný problém, ktorý súvisí s pohybom príšery, spôsobili KSPáci kŕmením.

Poznatky KSPákov súvisiace s prirodzeným prostredím príšer sú slabé. Skúšali kartónovú krabicu, plastové poháre, sklenenú karafu, sivú prútenú klietku, komoru skrytú pod kamenným stolom, plesnivú pivnicu, plechový kváder pokrytý strieborným plátnom, ktoré kedysi patrilo svetoznámemu kinu. Príšera pohrdla každým spomenutým priestorom. Správna potrava pre príšery? Príšerne podpriemerné poznatky prebývajú pod kučerami KSPáckych kotŕb. Sprvu sa KSPáci pokúšali kŕmiť príšeru kvasenou kyslou kapustou. Ktovie, prečo práve kyslú stravu skúsili KSPáci prvú. Pokus kŕmiť príšeru kapustou skončil katastrofou. Príšera sa priotrávila. Krátko potom stratila schopnosť korigovať smer svojho pohybu. Smutný príbeh. KSPáci potrebovali kompletne pozmeniť prístup. Snáď sa stav príšery polepší.

Po poradení sa s profesionálom posadili KSPáci svoju príšeru pod podlhovastú skrinku pokrývajúcu severnú stenu prastarej kúpeľne. Kopa prachu pod skrinkou poskytuje príšere príjemné pohodlie. Kúpeľňa sa prestala používať pred storočiami, preto se stala príbytkom poriadneho počtu pavúkov. Pavúky sú skvelým krmivom pre pažravú príšeru, pretože sú plné sviežich substancií. Krása. Sen pre pažravé príšery, ktoré sa snažia pribrať. Podlahu kúpeľne pokrýva \(k\) krát \(s\) kachličiek (\(s\) stĺpcov, každý s \(k\) kachličkami). Poniektoré kachličky sú prázdne, poniektoré sa pýšia pavúkom sediacim prostred kachličky.

Srstnaté končatiny príšery spôsobujú pavúkom strach. Keď sa príšera prvýkrát pozrie spod skrinky, poškrabká svojou krivou paprčou studenú kachličku, pavúky sa preľaknú. Každý pavúk sa pustí strečkovať smerom ku ktorejsi stene. Keď pribehnú ku kraju kúpeľne, schovajú sa pod podlahu. Preto príšera potrebuje pochytať pavúky počas svojej prvej prechádzky. Kvôli pokazenej koordinácii pohybov (spôsobenej priotrávením sa kyslou kapustou) stratila príšera schopnosť kráčať kľukato. Preto sa pohybuje po polpriamke kolmej so severnou stenou kúpeľne.

Príšera sa pohybuje súčasne s pavúkmi. Keď príšera spraví krok, pavúky spravia krok. Keď príšera prejde kachličku, pavúky prejdú kachličku.

Poznáte pozície pavúkov. Poznáte smer pohybu každého pavúka. Pre každý stĺpec kachličiek spočítajte počet pavúkov, ktoré príšera stretne, keď stĺpcom pôjde.

Úloha

Ako ste určite pochopili z predošlého textu, vedúci KSP si kúpili príšeru, ktorú ubytovali v starej opustenej kúpeľni. V tejto kúpeľni žijú pavúky a príšera by chcela nejaké z nich zjesť.

Kúpeľna obdĺžnikového tvaru je rozdelená na mriežku kachličiek rozmerov \(k\times s\). V kúpeľni je \(p\) pavúkov, každý sa nachádza uprostred niektorej kachličky. O každom pavúkovi viete jeho počiatočnú pozíciu a tiež smer jeho pohybu. Smer môže byť na sever, východ, západ alebo juh.

Príšera si vyberie nejaký zo stĺpcov a vykukne spod skrinky severne od prvej rady kachličiek. Potom sa bude pohybovať smerom na juh rovnako rýchlo ako pavúky. Kým sa dostane doprostred prvej kachličky, pavúky akurát prejdú vzdialenosť jednej kachličky. Vždy, keď stretne nejakého pavúka, zožerie ho a pokračuje ďalej v pohybe.

Pre každý stĺpec vypíšte, koľko pavúkov príšera zje, ak si vyberie daný stĺpec.

Formát vstupu

V prvom riadku vstupu sú tri čísla \(p\), \(k\) a \(s\) udávajúce počet pavúkov a rozmery kúpeľne.

Nasleduje \(p\) riadkov, na \(i\)-tom z nich sú dve čísla \(k_i\), \(s_i\) (\(1\leq k_i\leq k, 1\leq s_i\leq s\)) a písmeno. Pavúk sedí na začiatku v riadku \(k_i\) a stĺpci \(s_i\). Podľa toho, či je písmeno S, V, J alebo Z sa bude pavúk pohybovať na sever, východ, juh alebo západ. Smerom na juh stúpajú čísla riadkov a smerom na východ stúpajú čísla stĺpcov.

Pre jednotlivé vstupné sady platia nasledovné obmedzenia:

Formát výstupu

Vypíšte jeden riadok, na ktorom bude \(s\) čísel oddelených medzerami. Za posledným číslom nevypisujte medzeru. \(i\)-te z týchto čísel má byť počet pavúkov, ktoré by príšera zjedla, keby sa vybrala \(i\)-tym stĺpcom.

Príklad

Input:

4 4 5
1 1 V
3 2 V
1 4 J
4 5 S

Output:

0 1 0 0 2