ratina

Ratina

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

Limba ratina are doar $N$ cuvinte, numerotate de la $1$ la $N$. Doua sau mai multe cuvinte se numesc $k$-asemenea daca au primele $k$ litere identice. Gradul de asemanare intre $t$ cuvinte este $k$ daca cele $t$ cuvinte sunt $k$-asemenea, dar nu sunt $(k+1)$-asemenea.

Limba ratina are doar $N$ cuvinte, numerotate de la $1$ la $N$. Doua sau mai multe cuvinte se numesc $k-asemenea$ daca au primele $k$ litere identice. Gradul de asemanare intre $t$ cuvinte este $k$ daca cele $t$ cuvinte sunt $k-asemenea$, dar nu sunt $(k+1)-asemenea$.

h2. Cerinta

h2. Date de intrare
Fisierul de intrare $ratina.in$ va contine pe prima linie doua numere naturale $N M$, separate printr-un spatiu, reprezentand numarul de cuvinte din limba ratina, respectiv numarul de interogari.

Urmatoarele $N$ linii vor contine cuvintele din limba ratina, cate un cuvant pe o linie. Mai exact, pe linia $i+1 $este scris cuvantul cu numarul de ordine $i$. Cuvintele sunt formate din litere mici din alfabetul englez. Urmează $M$ linii, fiecare linie reprezentand cate o interogare exprimata astfel: primul numar de pe linie este un numar natural $t$ cuprins intre $2$ si $10$ reprezentand numarul de cuvinte din interogare, apoi vor urma cele $t$ numere de ordine ale cuvintelor din interogare, separate prin câte un spatiu.

Urmatoarele $N$ linii vor contine cuvintele din limba ratina, cate un cuvant pe o linie. Mai exact, pe linia $i+1$ este scris cuvantul cu numarul de ordine $i$. Cuvintele sunt formate din litere mici din alfabetul englez. Urmeaza $M$ linii, fiecare linie reprezentand cate o interogare exprimata astfel: primul numar de pe linie este un numar natural $t$ cuprins intre $2$ si $10$ reprezentand numarul de cuvinte din interogare, apoi vor urma cele $t$ numere de ordine ale cuvintelor din interogare, separate prin cate un spatiu.

h2. Date de iesire

h2. Restrictii

* $1 ≤ N ≤ 10 000$

* $1 ≤ N ≤ 10000$

* $1 ≤ lungimea maxima a unui cuvant ≤ 2000$

* $1 ≤ suma lungimilor tuturor cuvintelor ≤ 200 000$
* $1 ≤ M ≤ 100 000$

* $1 ≤ suma lungimilor tuturor cuvintelor ≤ 200000$
* $1 ≤ M ≤ 100000$

h2. Exemplu

Prima interogare cere gradul de asemanare intre cuvintele $asdf$ si $asdeffff$, care este 3 (deoarece cele doua cuvinte au primele 3 litere identice, dar nu si primele 4 litere).
Cea de a doua interogare cere gradul de asemanare intre cuvintele $gata$ si $gara$, care este 2.

Cea de a treia interogare cere gradul de asemanare intre cuvintele $pesistem$ ÅŸi $pestesistem$ care este 3.

Cea de a treia interogare cere gradul de asemanare intre cuvintele $pesistem$ si $pestesistem$ care este 3.

Cea de a patra interogare cere gradul de asemanare intre cuvintele $asdf$, $gata$ si $pesistem$ care este 0.
Ultima interogare este evidenta: un cuvant este $k$-asemenea cu el insusi unde $k$ este chiar lungimea cuvantului.
== include(page="template/taskfooter" task_id="ratina") ==

1761