5. Zázračné karty

Táto úloha sa dá nahradiť riešením sady conditions_cpp na Liahni (betaliahen.ksp.sk) . Ak chceš, aby ti namiesto bodov za riešenie tejto úlohy boli započítané body získané riešením spomínanej sady, na stránke odovdzaj pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy napíšte Michalovi ‘Žabovi’ Anderlemu na

Žaba má zázračné karty. Aspoň to tak tvrdí. V skutočnosti má úplne obyčajný balíček kariet, s ktorými robí všakovaké triky. Minule stretol Kozzu a jeden takýto trik mu predviedol. Karty premiešal, balíček párkrát prevrátil hore nohami, znovu premiešal… A na koniec Kozzu ohúril tým, že vedel presne povedať poradie, v akom karty sú. Kozza bol úplne nadšený. Hneď chcel, aby ho Žaba trik s kartami naučil. Žaba mu teda prezradil tajomstvo svojho úspechu: totiž, že na začiatku vedel, v akom poradí karty sú a keď ich miešal, vždy len zobral kartu zvrchu a dal ju na spodok, alebo zobral kartu zospodu a dal ju navrch, alebo celú kopu otočil hore nohami. Ako ale vedel tak rýchlo povedať, ako bude vyzerať finálne poradie? To si teraz naprogramujete!

Úloha

Každá karta je označená nejakým (nie nutne jedinečným) prirodzeným číslom. Máte zadaných \(n\) kariet, v poradí, v akom boli na začiatku v kope kariet, od spodku po vrch. Ďalej máme zadanú postupnosť \(q\) krokov: D – zoberieme kartu z vrchu kopy a presunieme ju dole, H – zoberieme kartu zospodu kopy a presunieme ju hore, a R – otočenie kopy (reverz). Pre dané poradie kariet na začiatku a postupnosť krokov zistite, v akom poradí budú karty na konci.

Formát vstupu

Na prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 1\,000\,000\)) a \(q\) (\(1 \leq q \leq 1\,000\,000\)) oddelené medzerou – počet kariet v kope a počet krokov miešania. Na ďalšom riadku je \(n\) medzerami oddelených čísel – čísla kariet v poradí, v akom boli na začiatku v kope od spodku po vrch. Čísla nepresiahnu \(1\,000\,000\) a môžu sa opakovať. Nasleduje riadok s \(q\) znakmi oddelenými medzerami. Každý znak popisuje jeden krok miešania – D (presun dole), H (presun hore) a R (reverz kopy).

Formát výstupu

Na výstup vypíšte \(n\) čísel – čísla kariet v poradí, v akom budú karty na konci triku v kope, odspodu po vrch.

Príklad

Input:

5 4
7 8 9 1 2
D D H R

Output:

1 9 8 7 2

Vykonávaním jednotlivých krokov sa bude poradie kariet v kope meniť nasledovne: \(7 8 9 1 2 \rightarrow 2 7 8 9 1 \rightarrow 1 2 7 8 9 \rightarrow 2 7 8 9 1 \rightarrow 1 9 8 7 2\)

Input:

3 7
1 2 3
R D D R H H R

Output:

1 3 2