Познато је да се Комисијска комисија за жалбе састоји од \(n\) чланова који раде за \(n\) столова нумерисаних, с лева удесно, бројевима од \(1\) до \(n\). Сваки члан комисије за жалбе поседује праведност, “Ја \(\heartsuit\) Петља” шољу и “Мрзим жалбе” мајицу. Кад год неки такмичар уобрази да је оштећен на такмичењу, он предаје жалбу неком члану комисије и нада се најбољем.

Међутим, чудни су путеви жалби. Када неки члан добије жалбу, он се згрози, баца новчић и, уколико падне писмо, прослеђује жалбу неком члану комисије лево од себе који није већ добио ову жалбу; уколико падне глава, прослеђује жалбу неком члану комисије десно од себе који није већ добио ову жалбу. Чланови комисије су навежбани у бацању новчића - жалба на овај начин увек прође све чланове комисије и, након \(n-1\) прослеђивања, члан који последњи добије ову жалбу је баца у канту за смеће и шаље мејл “жалба је одбијена”.

Зли такмичар Бежал Еверфор је добио “жалба је одбијена” мејл (тужна прича) и он жели да испита зашто је до тога дошло. Он је преварантским методама сазнао свих \(n-1\) резултата бацања новчића и циљ му је да на основу тога реконструише редослед прослеђивања жалбе тј. да пронађе пермутацију \((p_1, p_2, \ldots, p_n)\) бројева која означава да је жалбу прво добио члан \(p_1\) који је проследио члану \(p_2\) који је проследио \(\ldots\) који је проследио члану \(p_n\). Таква пермутација мора бити у складу са бацањем новчића (нпр. ако је у \(i\)-том бацању пало писмо, члан \(p_{i+1}\) мора имати мањи редни број од члана \(p_i\)); назовимо све такве пермутације (редоследе) добрим.

Осим жалби, Бежал много воли лексикографске поретке и конкретан број \(k\). Зато вас је замолио да му помогнете у реконструкцији редоследа прослеђивања жалби:

• Уколико пронађете лексикографски најмању од свих добрих пермутација које почињу бројем \(k\) (тј. за које важи \(p_1 = k\)) добијате све поене на одговарајућем тест-примеру.
• Уколико пронађете било коју добру пермутацију која не задовољава све горе поменуте услове добијате 60% поена на одговарајућем тест-примеру. (дакле, у овом случају не треба обраћати пажњу на број \(k\) и лексикографски поредак али пермутација и даље мора бити у складу са бацањем новчића).

Уколико помогнете Бежалу, добијате половину усвојених поена са његове жалбе!

Опис улаза

У првом реду стандардног улаза налазе се природни бројеви \(n\) и \(k\), одвојени размаком. У другом реду налази се \(n-1\) карактера који су или ‘P’ (писмо, означава прослеђивање жалбе улево) или ‘G’ (глава, означава прослеђивање жалбе удесно). Између карактера нема размака.

Опис излаза

У први и једини ред стандардног излаза исписати \(n\) различитих природних бројева од \(1\) до \(n\) - тражену пермутацију \(p\). Улазни подаци ће бити такви да ће решење (за максималан број поена) увек постојати - то решење је (јасно) увек јединствено док је за 60% поена дозвољено исписати било које (тачно) решење.

Пример 1

Улаз

5 2
GPPG

Излаз

2 4 3 1 5

Пример 2

Улаз

3 3
PP

Излаз

3 2 1

Објашњење примера

У првом примеру је \(n = 5\), \(k = 2\) а бацање новчића каже да је жалба путовала десно-лево-лево-десно. Тражена лексикографски минимална пермутација која почиње од \(k\)-тог члана је (2, 4, 3, 1, 5) тј. члан 2 прослеђује (удесно) члану 4, овај прослеђује (улево) члану 3, овај прослеђује (улево) члану 1, овај прослеђује (удесно) члану 5. Ово решење осваја све поене док нека од решења која освајају 60% поена могу бити (3, 5, 2, 1, 4) (не почиње од \(k\)-тог члана) и (2, 5, 4, 1, 3) (није лексикографски минимална пермутација који почиње бројем \(k\)).

Ограничења

• \(2 \leq n \leq 200.000\)
• \(1 \leq k \leq n\)
• Свих \(n-1\) карактера на улазу припадају скупу \(\{'P', 'G'\}\)

Тест примери су подељени у пет дисјунктних група:

• У тест примерима који вреде \(10\) поена важиће \(n \leq 4\).
• У тест примерима који вреде \(15\) поена важиће \(n \leq 10\).
• У тест примерима који вреде \(15\) поена важиће \(n \leq 5.000\).
• У тест примерима који вреде \(30\) поена гарантује се да најмања лексикографска пермутација која је сагласна са резултатима бацања новћића почиње управо бројем \(k\).
• У тест примерима који вреде \(30\) поена нема додатних ограничења.

Напомена

Низ \((a_1, a_2, a_3, \ldots, a_n)\) је лексикографски мањи од низа \((b_1, b_2, b_3, \ldots, b_n)\) ако постоји индекс \(i\) са особином да је \(a_1 = b_1, a_2 = b_2, \ldots, a_{i-1} = b_{i-1}\) и \(a_{i} < b_{i}\).