Ž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
Odovzdávanie
Na odovzdávanie sa musíš prihlásiť
Otázky a diskusia
Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.