Facebook Search

fbsearch

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

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$ operatii:
 
* $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).

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $fbsearch.in$ contine pe prima linie $T$, numarul de teste. In continuare, pentru fiecare test se vor gasi:
 
Pe prima linie $N$, numarul de utilizatori si $M$, numarul de operatii.
Pe urmatoarele $N$ linii, utilizatorii.
Pe urmatoarele $M$ linii urmeaza operatiile descrise.

Fişierul de intrare $fbsearch.in$ ...

h2. Date de ieşire

În fişierul de ieşire $fbsearch.out$ se vor afisa raspunsurile la intrebarile de tip $Q$.
Daca nu exista niciun raspuns se va afisa "Search Bing for $X$", unde $X$ este stringul cautat.

În fişierul de ieşire $fbsearch.out$ ...

h2. Restricţii

* $1 ≤ T ≤ 3$
* $1 ≤ N ≤ 100 000$
* $1 ≤ M ≤ 100 000$
* $0 ≤ R ≤ 10$
* Utilizatorii si intrebarile nu vor avea mai mult de 32 de caractere, si nu contin decat caractere ale alfabetului englez şi caracterul "_" (fara spatii).
* Nu se tine cont de litere mari la cautari, dar utilizatorii trebuie afisati ca in fisierul de intrare.
* Initial relevanta este 0 pentru toti utilizatorii.

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. fbsearch.in |_. fbsearch.out |

| 1
5 7
AndreiPopescu
GiuliaMateescu
AndreiAnton
Teo
Teodor
Q An
Q BiEnCuTzA
U AndreiPopescu 1
Q andr
Q Teo
U Teodor 1
Q Teo
| AndreiAnton
  Search Bing for BiEnCuTzA
  AndreiPopescu
  Teo
  Teodor

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|

h3. Explicaţie
 
...

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

9531