Obeleži sve kategorije koje odgovaraju problemu

Poznato je da se Komisijska komisija za žalbe sastoji od $n$ članova koji rade za $n$ stolova numerisanih, s leva udesno, brojevima od $1$ do $n$. Svaki član komisije za žalbe poseduje pravednost, "Ja $\heartsuit$ Petlja" šolju i "Mrzim žalbe" majicu. Kad god neki takmičar uobrazi da je oštećen na takmičenju, on predaje žalbu nekom članu komisije i nada se najboljem.

Međutim, čudni su putevi žalbi. Kada neki član dobije žalbu, on se zgrozi, baca novčić i, ukoliko padne pismo, prosleđuje žalbu nekom članu komisije levo od sebe koji nije već dobio ovu žalbu; ukoliko padne glava, prosleđuje žalbu nekom članu komisije desno od sebe koji nije već dobio ovu žalbu. Članovi komisije su navežbani u bacanju novčića - žalba na ovaj način uvek prođe sve članove komisije i, nakon $n-1$ prosleđivanja, član koji poslednji dobije ovu žalbu je baca u kantu za smeće i šalje mejl "žalba je odbijena".

Zli takmičar Bežal Everfor je dobio "žalba je odbijena" mejl (tužna priča) i on želi da ispita zašto je do toga došlo. On je prevarantskim metodama saznao svih $n-1$ rezultata bacanja novčića i cilj mu je da na osnovu toga rekonstruiše redosled prosleđivanja žalbe tj. da pronađe permutaciju $(p_1, p_2, \ldots, p_n)$ brojeva koja označava da je žalbu prvo dobio član $p_1$ koji je prosledio članu $p_2$ koji je prosledio $\ldots$ koji je prosledio članu $p_n$. Takva permutacija mora biti u skladu sa bacanjem novčića (npr. ako je u $i$-tom bacanju palo pismo, član $p_{i+1}$ mora imati manji redni broj od člana $p_i$); nazovimo sve takve permutacije (redoslede) dobrim.

Osim žalbi, Bežal mnogo voli leksikografske poretke i konkretan broj $k$. Zato vas je zamolio da mu pomognete u rekonstrukciji redosleda prosleđivanja žalbi:

• Ukoliko pronađete leksikografski najmanju od svih dobrih permutacija koje počinju brojem $k$ (tj. za koje važi $p_1 = k$) dobijate sve poene na odgovarajućem test-primeru.
• Ukoliko pronađete bilo koju dobru permutaciju koja ne zadovoljava sve gore pomenute uslove dobijate 60% poena na odgovarajućem test-primeru. (dakle, u ovom slučaju ne treba obraćati pažnju na broj $k$ i leksikografski poredak ali permutacija i dalje mora biti u skladu sa bacanjem novčića).

Ukoliko pomognete Bežalu, dobijate polovinu usvojenih poena sa njegove žalbe!

Opis ulaza

U prvom redu standardnog ulaza nalaze se prirodni brojevi $n$ i $k$, odvojeni razmakom. U drugom redu nalazi se $n-1$ karaktera koji su ili 'P' (pismo, označava prosleđivanje žalbe ulevo) ili 'G' (glava, označava prosleđivanje žalbe udesno). Između karaktera nema razmaka.

Opis izlaza

U prvi i jedini red standardnog izlaza ispisati $n$ različitih prirodnih brojeva od $1$ do $n$ - traženu permutaciju $p$. Ulazni podaci će biti takvi da će rešenje (za maksimalan broj poena) uvek postojati - to rešenje je (jasno) uvek jedinstveno dok je za 60% poena dozvoljeno ispisati bilo koje (tačno) rešenje.

Primer 1

Ulaz

5 2
GPPG

Izlaz

2 4 3 1 5

Primer 2

Ulaz

3 3
PP

Izlaz

3 2 1

Objašnjenje primera

U prvom primeru je $n = 5$, $k = 2$ a bacanje novčića kaže da je žalba putovala desno-levo-levo-desno. Tražena leksikografski minimalna permutacija koja počinje od $k$-tog člana je (2, 4, 3, 1, 5) tj. član 2 prosleđuje (udesno) članu 4, ovaj prosleđuje (ulevo) članu 3, ovaj prosleđuje (ulevo) članu 1, ovaj prosleđuje (udesno) članu 5. Ovo rešenje osvaja sve poene dok neka od rešenja koja osvajaju 60% poena mogu biti (3, 5, 2, 1, 4) (ne počinje od $k$-tog člana) i (2, 5, 4, 1, 3) (nije leksikografski minimalna permutacija koji počinje brojem $k$).

Ograničenja

• $2 \leq n \leq 200.000$
• $1 \leq k \leq n$
• Svih $n-1$ karaktera na ulazu pripadaju skupu $\{'P', 'G'\}$

Test primeri su podeljeni u pet disjunktnih grupa:

• U test primerima koji vrede $10$ poena važiće $n \leq 4$.
• U test primerima koji vrede $15$ poena važiće $n \leq 10$.
• U test primerima koji vrede $15$ poena važiće $n \leq 5.000$.
• U test primerima koji vrede $30$ poena garantuje se da najmanja leksikografska permutacija koja je saglasna sa rezultatima bacanja novćića počinje upravo brojem $k$.
• U test primerima koji vrede $30$ poena nema dodatnih ograničenja.

Napomena

Niz $(a_1, a_2, a_3, \ldots, a_n)$ je leksikografski manji od niza $(b_1, b_2, b_3, \ldots, b_n)$ ako postoji indeks $i$ sa osobinom da je $a_1 = b_1, a_2 = b_2, \ldots, a_{i-1} = b_{i-1}$ i $a_{i} < b_{i}$.