Code Submission Evaluation System Login

IOI-leiri 2016

Treap II


Task | Statistics


CSES - Treap IICSES - Treap II

Time limit:2.00 s Memory limit:256 MB

Uolevilla on merkkijono, joka muodostuu kirjaimista A, H, I, M, O, T, U, V, W, X ja Y. Hän muodostaa leikkailemalla ja liimailemalla uuden merkkijonon käyttäen seuraavia operaatioita: Kaikki merkkijonot numeroidaan siten, että alkuperäinen merkkijono on 0, ja operaatioissa syntyvät merkkijonot numeroidaan juoksevasti (S-operaatiossa luotavista kahdesta merkkijonosta alkuosa tulee ennen loppuosaa). Käsiteltävät merkkijonot tuhoutuvat operaatiossa, eli samaa merkkijononumeroa ei käytetä useampaa kertaa. Kun kaikki operaatiot on suoritettu, kaikki merkkijonot on taas yhdistetty yhdeksi merkkijonoksi. Tehtäväsi on selvittää, mikä tämä merkkijono on.

Syöte

Syötteen ensimmäisellä rivillä on Uolevin alkuperäinen merkkijono. Syötteen toinen rivi sisältää operaatioiden lukumäärän $q$. Loput $q$ riviä sisältävät operaatiot. Operaatiorivin ensimmäinen kirjain kuvaa operaation tyypin (S, M tai R). Rivillä on tämän lisäksi luvut $a$ ja $b$.
Tuloste

Tulosta yksi rivi, joka sisältää lopuksi jäljelle jäävän merkkijonon.

Rajat
Esimerkki

Syöte:
HVIUYAOTMH
10
S 0 7
S 1 4
S 2 2
M 4 5
R 7 3
S 8 6
M 9 6
S 11 2
R 13 10
M 12 14


Tuloste:
UIYAOHTMHV