FMI NO STRESS 13 | PHF

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 $1$ la $N$, 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 $1$ și $2$. Câștigătorul acestui meci va juca mai departe cu jucătorul $3$. Câștigătorul acestui meci va juca mai departe cu jucătorul $4$, și tot așa până la ultimul meci, la care va lua parte și jucătorul $N$. Un jucător are ales încă de la început un mod de joc ($P$, $H$ sau $F$) 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 $\text{P}$, iar celălalt modul de joc $\text{H}$, atunci câștigă cel ce folosește $\text{H}$ (hârtia acoperă piatra);
• Dacă unul dintre concurenți folosește modul de joc $\text{H}$, iar celălalt modul de joc $\text{F}$, atunci câștigă cel ce folosește $\text{F}$ (foarfeca taie hârtia);
• Dacă unul dintre concurenți folosește modul de joc $\text{F}$, iar celălalt modul de joc $\text{P}$, atunci câștigă cel ce folosește $\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 $3$ 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, $N$ și $Q$, cu semnificațiile din enunț. Pe următoarea linie se găsesc $N$ caractere din mulțimea $\{\text{P}, \text{H}, \text{F}\}$ neseparate prin spațiu. Pe următoarele $Q$ linii se găsesc schimbările, un număr $i$ urmat de un spațiu, și un caracter $M$, unde $i$ este indicele concurentului ce se presupune a-și modifica modul de joc, iar $M$ 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 $i$-lea caracter va conține modul de joc al câștigătorului olimpiadei după ce primele $i$ schimbări au avut loc.

Restricții și precizări

• $2 \le N \le 10^6$;
• $1 \le Q \le 10^5$;
• Pentru fiecare schimbare $1 \le i \le N$, $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 $31$ de puncte, $N, Q \le 5 \ 000$;
• Pentru alte teste în valoare de $33$ de puncte, $N + Q \le 70 \ 000$;
• Pentru alte teste în valoare de $36$ de puncte, nu există restricții suplimentare.

Exemplu

stdin

5 3
PHFPP
5 H
4 F
5 P

stdout

PHFP

Explicație

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

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

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

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

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