robot

În viitor Concursul "Urmaşii lui Moisil" va avea, cu siguranţă, şi o secţiune de robotică. Anul acesta însă nu trebuie să proiectaţi un robot, trebuie doar să scrieţi aplicaţia pentru robotul respectiv.

Robotul nostru, să-l numim Moisil, în onoarea patronului acestui concurs, procesează un șir $v$ format din $n$ numere întregi, indexate de la $1$ la $n$.

Notăm cu $v_{st \dots dr}$ secvența formată din elementele $v_{st}, v_{st+1}, \dots, v_{dr}$. Definim frecvența unei valori într-o secvență ca fiind numărul de apariții ale acelei valori în secvența respectivă.

O întrebare este definită printr-o pereche de valori $st\ dr$ ($1 \le st \le dr \le n$) şi solicită robotului să afişeze un mesaj referitor la frecvenţa valorilor din secvenţa $v_{st \dots dr}$.

Mesajele care se afişează depind de modul de funcţionare selectat pentru robot. Înainte de a primi lista de întrebări, se stabileşte un mod de funcţionare, iar robotul va răspunde în funcţie de modul de funcţionare selectat. Există 3 moduri de funcţionare posibile:

• High. În acest mod robotul poate furniza, la fiecare întrebare, unul dintre următoarele $4$ mesaje:

• Medium. În acest mod robotul poate furniza, la fiecare întrebare, unul dintre următoarele $3$ mesaje:

• Low. În acest mod robotul poate furniza, la fiecare întrebare, unul dintre următoarele $2$ mesaje:

Cerință

Scrieţi un program care selectează un mod de funcţionare pentru robot şi afişează răspunsurile date de robot în modul de funcţionare ales pentru o listă de $q$ întrebări.

Date de intrare

Fişierul de intrare robot.in conţine pe prima linie numerele naturale $n$ și $q$, având semnificaţia din enunţ. A doua linie conține $n$ numere întregi, care reprezintă elementele $v_1, v_2, \dots, v_n$. Pe următoarele $q$ linii se află cele $q$ întrebări, în forma descrisă în enunţ, câte o întrebare pe o linie. Valorile scrise pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire robot.out conţine $q+1$ linii. Pe prima linie este scrisă litera H, M sau L, după cum modul de funcţionare selectat pentru robot este High, Medium sau Low. Pe următoarele $q$ linii sunt scrise, în ordine, mesajele afişate de robot ca răspuns la cele $q$ întrebări din fişierul de intrare.

Restricții și precizări

• $1 \le n, q \le 200\ 000$
• $-10^9 \le v_i \le 10^9$, pentru orice $1 \le i \le n$
• Dacă modul de funcționare selectat pentru robot este Low, se acordă 50% din punctajul pe test.
• Dacă modul de funcționare selectat pentru robot este Medium, se acordă 80% din punctajul pe test.
• Dacă modul de funcționare selectat pentru robot este High, punctajul pe test se acordă integral.

Exemplu

robot.in

10 4
1 2 3 1 2 2 3 3 3 1
3 5
1 5
1 6
5 8

robot.out (modul High)

H
!1
!1!2
x
!2

robot.out (modul Medium)

M
!1
?1!2
x
?1!2

robot.out (modul Low)

L
!1
x
x
x

Explicație

Prima întrebare este $3\ 5$. În secvenţa $v_{3 \dots 5}$ apar $3$ valori ($1$, $2$ şi $3$) fiecare având frecvenţa $1$. În toate cele 3 moduri de funcţionare robotul va afişa mesajul !1.

A doua întrebare este $1\ 5$. În secvenţa $v_{1 \dots 5}$ există $3$ valori ($1$, $2$ şi $3$), având frecvenţele $2$, $2$, respectiv $1$. În modul High robotul va răspunde !1!2, în modul Medium robotul va răspunde ?1!2, iar în modul Low robotul va răspunde x.

A treia întrebare este $1\ 6$. În secvenţa $v_{1 \dots 6}$ există $3$ valori ($1$, $2$ şi $3$), având frecvenţele $2$, $3$, respectiv $1$. În toate cele 3 moduri mesajul afişat este x.

A patra întrebare este $5\ 8$. În secvenţa $v_{5 \dots 8}$ există $2$ valori ($2$ şi $3$), fiecare având frecvenţa $2$. În modul High robotul va răspunde !2, în modul Medium robotul va răspunde ?1!2, iar în modul Low robotul va răspunde x.