== include(page="template/taskheader" task_id="fbsearch") ==

Pentru aceasta problema va trebui sa implementati functia de cautare de la Facebook. Atunci cand scriem numele unei persoane, Facebook ne da sugestii inca de la prima litera introdusa. Aceste sugestii sunt personalizate in functie de relevanta lor pentru fiecare utilizator. Astfel daca Traian scrie "e" va fi autocompletat "Emil Boc", iar daca Vasile scrie "e" va fi autocompletat "Elena Popescu".

Pentru aceasta problema va trebui sa implementati functia de cautare de la Facebook pentru un utilizator. Atunci cand scriem numele unei persoane, Facebook ne da sugestii inca de la prima litera introdusa. Aceste sugestii sunt personalizate in functie de relevanta lor pentru fiecare utilizator. Astfel daca Traian scrie "e" va fi autocompletat "Emil Boc", iar daca Vasile scrie "e" va fi autocompletat "Elena Popescu".

Se vor da $M$ autentificari apoi $K$ operatii pentru utilizatorul curent:

Se vor da $M$ operatii:

* $L User K$ - Se autentifica utilizatorul specificat, si urmeaza $K$ operatii pentru acesta:
** $Q X$ - Afiseaza rezultatul cautarii pentru stringul $X$ introdus, in functie de relevanta. Daca doi utilizatori au aceeasi relevanta se va afisa cel mai mic (lexicografic).
** $U User R$ - La relevanta utilizatorului specificat pentru utilizatorul curent se adauga $R$ (acesta este in functie de interese comune, proximitate, like-uri etc).

* $Q X$ - Afiseaza rezultatul cautarii pentru stringul $X$ introdus, in functie de relevanta. Daca doi utilizatori au aceeasi relevanta se va afisa cel mai mic (lexicografic).
* $U User R$ - La relevanta utilizatorului specificat se adauga $R$ (acesta este in functie de interese comune, proximitate, like-uri etc).

h2. Date de intrare

Pe prima linie $N$, numarul de utilizatori.
Pe urmatoarele $N$ linii, utilizatorii.

Pe urmatoarea linie $M$, numarul de autentificari.
Pe urmatoarele linii urmeaza operatiile descrise.

Pe urmatoarele $M$ linii urmeaza operatiile descrise.

h2. Date de ieşire

h2. Restricţii
* $1 ≤ N ≤ 100 000$

* $1 ≤ M ≤ 10$
* $-1000 ≤ R ≤ 1000$
* Numarul total de operatii nu va depasi $100 000$
/* Utilizatorii si query-urile nu vor depasi 32 de caractere.

* $1 ≤ M ≤ 100 000$
* $-10 ≤ R ≤ 10$
* Utilizatorii si intrebarile nu vor avea mai mult de 32 de caractere, si nu contin spatii. Doar caractere ale alfabetului englez si "$_$".

* Nu se tine cont de litere mari la cautari, dar utilizatorii trebuie afisati ca in fisierul de intrare.

* Spatiile sunt reprezentate prin "$_$"

* Initial relevanta este 0 pentru toti utilizatorii.
h2. Exemplu

Andrei_Anton
Teo
Teodor

2
L Giulia_Mateescu 4

7

Q An
Q BiEnCuTzA
U Andrei_Popescu 1
Q andr

L Andrei_Popescu 3

Q Teo
U Teodor 1
Q Teo