FMI NO STRESS 13 | PHF

This was the problem page during the contest. Access the current page here.
Time limit: 0.25s Memory limit: 256MB Input: Output:

ONPHF (Olimpiada Națională de Piatră, Hârtie, Foarfecă) este o competiție la nivel național, îndrăgită de mulți pentru simplitate și pentru cât de ușor este să participi, astfel că de obicei sunt mulți concurenți. Aceștia vor fi numerotați de la 11 la NN, pentru a-i distinge ușor.

Olimpiada constă într-o serie de meciuri de Piatră, Hârtie, Foarfecă. Primul meci se desfășoară între jucătorii 11 și 22. Câștigătorul acestui meci va juca mai departe cu jucătorul 33. Câștigătorul acestui meci va juca mai departe cu jucătorul 44, și tot așa până la ultimul meci, la care va lua parte și jucătorul NN. Un jucător are ales încă de la început un mod de joc (PP, HH sau FF) cu care va juca în toate meciurile la care ia parte.

Câștigătorul meciului este determinat prin următoarele reguli:

  • Dacă unul dintre concurenți folosește modul de joc P\text{P}, iar celălalt modul de joc H\text{H}, atunci câștigă cel ce folosește H\text{H} (hârtia acoperă piatra);
  • Dacă unul dintre concurenți folosește modul de joc H\text{H}, iar celălalt modul de joc F\text{F}, atunci câștigă cel ce folosește F\text{F} (foarfeca taie hârtia);
  • Dacă unul dintre concurenți folosește modul de joc F\text{F}, iar celălalt modul de joc P\text{P}, atunci câștigă cel ce folosește P\text{P} (piatra sparge foarfeca);
  • Dacă ambii jucători folosesc același mod de joc, atunci câștigă cel cu indicele mai mic (se presupune că a câștigat mai multe jocuri până acum, deci are prioritate).

Cerință

Deoarece speculațiile sunt o parte frumoasă a competiției, comisia se întreabă cum s-ar desfășura jocul dacă anumiți jucători și-ar putea schimba alegerea (schimbările sunt cumulative, după a doua schimbare atât prima cât și a doua schimbare au efect). Din pricina numărului mare de participanți și modificări, aceasta a decis să scrie un program ce va calcula câștigătorul. Întrucât este ora 33 dimineața și comisia este ocupată cu găsirea unei soluții la Ants in the Matrix, vă roagă pe voi să scrieți acest program.

Date de intrare

Pe prima linie se află două numere naturale, NN și QQ, cu semnificațiile din enunț. Pe următoarea linie se găsesc NN caractere din mulțimea {P,H,F}\{\text{P}, \text{H}, \text{F}\} neseparate prin spațiu. Pe următoarele QQ linii se găsesc schimbările, un număr ii urmat de un spațiu, și un caracter MM, unde ii este indicele concurentului ce se presupune a-și modifica modul de joc, iar MM este noul mod de joc al concurentului.

Date de ieșire

Primul caracter va reprezenta modul de joc al câștigătorului înainte de prima schimbare. După aceasta, al ii-lea caracter va conține modul de joc al câștigătorului olimpiadei după ce primele ii schimbări au avut loc.

Restricții și precizări

  • 2N1062 \le N \le 10^6;
  • 1Q1051 \le Q \le 10^5;
  • Pentru fiecare schimbare 1iN1 \le i \le N, M{P,H,F}M \in \{\text{P}, \text{H}, \text{F}\};
  • Este posibil ca noul mod de joc al unui concurent să fie același cu cel vechi;
  • Pentru teste în valoare de 3131 de puncte, N,Q5 000N, Q \le 5 \ 000;
  • Pentru alte teste în valoare de 3333 de puncte, N+Q70 000N + Q \le 70 \ 000;
  • Pentru alte teste în valoare de 3636 de puncte, nu există restricții suplimentare.

Exemplu

stdin

5 3
PHFPP
5 H
4 F
5 P

stdout

PHFP

Explicație

Primii 33 jucători nu își schimbă niciodată modul de joc, deci după primele două meciuri va câștiga mereu F\text{F}.

Inițial al 44-lea jucător câștigă meciul cu jucătorul 33 și după și cu jucătorul 55, deci primul răspuns este P\text{P}.

După prima schimbare jucătorul 55 îl va învinge pe jucătorul 44 deci al doilea răspuns este H\text{H}.

După a doua schimbare jucătorul 44 va fi învins de jucătorul 33 care îl va învinge și pe 55, deci al treilea răspuns este F\text{F}.

După a treia schimbare jucătorul 55 îl va învinge pe 33, deci ultimul răspuns este P\text{P}.

Log in or sign up to be able to send submissions!