Rps

Dezamăgită de rezultatul de la ONI 2013, Miruna s-a gîndit să își încerce norocul la campionatul mondial de ”Rock-Paper-Scissors”. Pentru cei care nu sunt familiarizați cu jocul, regulile sunt următoarele:

• Întotdeauna se vor înfrunta direct doi jucători.
• Pentru a decide învingătorul unei runde, cei doi vor face anumite gesturi în același timp folosindu-și mîinile:
  • Palma întinsă reprezintă hîrtia.
  • Două degete întinse reprezintă foarfecele.
  • Pumnul strîns reprezintă piatra.
    
• Piatra bate foarfecele, foarfecele bate hîrtia iar hîrtia bate piatra.
• În cazul în care ambii jucători fac aceeași alegere, runda se termină remiză.

La această ediție a campionatului mondial organizatorii vor să evite pe cît posibil confruntările care se termină remiză. Drept urmare au decis ca orice meci să se joace în maximum $K$ runde: va fi declarat cîștigător primul jucător care reușește să cîștige o rundă. Dacă în toate cele $K$ runde cei doi fac aceleași alegeri, atunci confruntarea dintre ei este declarată remiză. O victorie valorează $W$ puncte, o remiză $D$ puncte, iar o înfrîngere nu schimbă punctajul total al unui concurent. Sistemul de joc este sub formă de campionat, ceea ce înseamnă că Miruna se va înfrunta pe rînd cu toți ceilalți $N$ concurenți.

Spre deosebire de celelalte competiții de ”Rock-Paper-Scissors” din lume, la acest campionat mondial jucătorii nu au voie să facă alegerile în mod aleator. În schimb, înainte de începutul campionatului, ei trebuie să prezinte juriului o serie de exact $K$ opțiuni pentru cele $K$ runde, urmînd ca în fiecare confruntare să facă aceleași alegeri. Practic, membrii juriului vor ști rezultatul oricărei confruntări încă dinaintea startului campionatului.

Fiind o ființă matinală, asemenea concurenților de la ONI 2013, Miruna se trezește de dimineață în ziua concursului și ajunge prima la locul desfășurării probei. Folosindu-și farmecele ei nemaipomenite, Miruna poate să citească mințile adversarilor săi. De fiecare dată cînd un alt concurent sosește la locul desfășurării probei ea poate afla seria de $K$ opțiuni pe care acesta le va prezenta juriului. Folosindu-se de aceste informații, Miruna vrea să găsească o strategie care să îi maximizeze scorul.

Din nefericire, Miruna nu cunoaște numărul total $N$ al concurenților înscriși la probă, așa că de fiecare dată cînd sosește un nou concurent, ea își regîndește strategia optimă care îi maximizează scorul (adică să obțină cît mai multe puncte în confruntarea cu acei concurenți care au ajuns deja la locul desfășurării probei). Vouă vi se cere să implementați un program care să o ajute pe Miruna.

Cerință

Se dau $N$ liste de lungime $K$, reprezentînd opțiunile concurenților în ordinea în care aceștia sosesc la proba de concurs. Fiecare listă va fi formată din caracterele R, P și S cu următoarea semnificație:

• R — piatră (rock)
• P — hîrtie (paper)
• S — foarfece (scissors)

Programul vostru va afișa tot $N$ liste de lungime $K$, formate din caracterele R, P și S, reprezentînd strategia optimă a Mirunei la fiecare moment de timp cînd sosește un concurent nou. În cazul în care există mai multe strategii optime, trebuie să o afișați pe cea minim lexicografică.

Restricții și precizări

• $1 \leq N, K$
• $1 \leq N * K \leq 1\ 000\ 000$
• $-1\ 000 \leq W, D \leq 1\ 000$
• Mirunei îi place doar î din i.

Date de intrare

Pe prima linie a fișierului rps.in se vor afla numerele $N$, $K$, $W$ și $D$, cu semnificația din enunț.
Următoarele $N$ linii vor conține cîte un șir de lungime $K$ format din caracterele R, P și S, reprezentînd opțiunile concurenților.

Date de ieșire

În fișierul rps.out se vor afișa $N$ linii, fiecare conținînd răspunsul cerut la fiecare moment de timp.

Exemplu

rps.in

4 3 2 1
RSP
PPP
SSP
SRR

rps.out

PPP
PPS
PPS
RRP

Explicație

Strategiile din fișierul de ieșire îi garantează Mirunei scorurile $2$, $4$, $4$ și $6$. Acestea sunt scorurile maxime care pot fi obținute, iar soluțiile prezentate sunt minime din punct de vedere lexicografic.