2. Organizácia Kapustnice

Ako každý rok, aj teraz sa konala KSP kapustnica. Paulinka sa rozhodla, že ku každému správnemu vianočnému posedeniu patria torty a nejaké preto upiekla, doniesla a rozložila na stôl.

Torty sú servírované na jednom dlhom stole a vedúci sa pre ne zoradili do radu. Každý vedúci sa hýbe v rade zľava doprava, kým sa nedostane k voľnej torte, potom si vezme tortu a odíde z radu zjesť tortu.

Paulinka si ale všimla, že nenapiekla správny počet toriet. Chcela by pridať nejaké torty, a/alebo zavolať pár vedúcich zo Suši, nech si tiež dajú torty. Chcela by to ale urobiť čo najrýchlejšie, nech aj ona si môže užívať kapustnicu. Pomôžte jej!

Úloha

Vedúci a torty si vieme predstaviť ako reťazec z písmen “V” – reprezentujúcich vedúcich v rade, a “T” – reprezentujúcich torty na stole. Pre jednoduchosť, nemôže sa stať, že je torta a vedúci na rovnakom mieste.

Vedúci zje najbližšiu nezjedenú tortu napravo od neho (napr. ak je na pozícii 5, potom vie zjesť torty na pozíciách od 6 vyššie) – pokiaľ ju už niekto pred ním nezjedol.

Paulinka by chcela pridať na stôl (medzi existujúce torty a vedúcich) niekoľko ďalších tort (čo najmenej) a/alebo zavolať nejakých Suši vedúcich (čo najmenej) – na hocijaké miesto v rade tak, aby každý vedúci skončil s presne jednou tortou.

Vypíšte, ako torty, resp. nových vedúcich zaradiť do radu - teda zistite, ako by mohla vyzerať situácia, aby pridaných toriet+vedúcich bolo spolu čo najmenej.

Formát vstupu

V prvom riadku vstupu je číslo \(n\) (\(1 \leq n \leq 10^6\)) udávajúce dĺžku reťazca na vstupe (počet vedúcich plus počet tort).

V druhom riadku vstupu sa nachádza reťazec z písmen “V” a “T” reprezentujúci počiatočnú situáciu pri stole.

V jednotlivých sadách platia nasledujúce obmedzenia:

V prvých dvoch sadách navyše stačí, aby tvoj program vrátil ľubovoľné správne riešenie, počet pridaných toriet a vedúcich nemusí byť nutne najmenší.

Formát výstupu

Vypíš jeden riadok a v ňom reťazec z písmen “V” a “T” reprezentujúci, ako by mala Paulinka upraviť situáciu, aby každý dostal práve jednu tortu.

Príklady

Input:

5
VTVTT

Output:

VTVTVT

Stačí pridať jedného vedúceho, ktorý zje tortu navyše. Ďalšie správne riešenie je napríklad VVTVTT

Input:

6
TVVVTT

Output:

VTVTVVTT