Fie un şir de caractere $S$. Numim bâlbâială de ordin $k$ a lui $S$ şirul obţinut prin multiplicarea fiecărui caracter al lui $S$ de exact $k$ ori. Spre exemplu, bâlbâiala de ordin $2$ a şirului "andrei" este şirul "aannddrreeii", iar bâlbâiala de ordin $3$ a şirului "ana" este şirul "aaannnaaa".

Fie un şir de caractere $A$ şi $Q$ şiruri de caractere B{~1~}, B{~2~}, .. B{~Q~}. Pentru fiecare şir $B$, dorim să aflăm bâlbâiala de ordin maxim a respectivului şir care apare ca subşir în şirul $A$. Spre exemplu, pentru $A = "onomatopee" şi $B = "oe"$, ordinul maxim al bâlbâielii este egal cu $2$.

Fie un şir de caractere $A$ şi $Q$ şiruri de caractere B{~1~}, B{~2~}, .. B{~Q~}. Pentru fiecare şir $B$, dorim să aflăm bâlbâiala de ordin maxim a respectivului şir care apare ca subşir în şirul $A$. Spre exemplu, pentru $A = "onomatopee"$ şi $B = "oe"$, ordinul maxim al bâlbâielii este egal cu $2$, iar pentru $B' = "z"$, ordinul maxim al bâlbâielii este egal cu $0$.

h2. Date de intrare

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

Fişierul de intrare $balbaiala.in$ contine pe prima linie numerele naturale $N$ (marimea sirului $A$) si $Q$ (numarul de siruri $B{~i~}$), pe a doua linie sirul $A$ de caractere, iar pe urmatoarele $Q$ linii sirurile $B{~i~}$.

h2. Date de ieşire

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

În fişierul de ieşire $balbaiala.out$ se vor afla $Q$ linii, pe a $i$-a dintre ele fiind un numar natural reprezentand ordinul maxim al bâlbâielii sirului $B{~i~}$ care sa apara ca subsir in sirul $A$.

h2. Restricţii

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

* Suma lungimilor celor Q query-uri este mai mica sau egala cu $300.000$
* Pentru $20$ de puncte, $1 ≤ N, Q ≤ 100$
* Pentru $40$ de puncte, $1 ≤ N, Q ≤ 5.000$
* Pentru $70$ de puncte, $1 ≤ N ≤ 30.000$ si $1 ≤ Q ≤ 40.000$
* Pentru toate punctele, $1 ≤ N, Q ≤ 100.000$

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

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

| 13 3
abbbaababbaaa
ab
ba
aba
| 3
4
3

|
h3. Explicaţie

...

* $ab$ - Bâlbâiala de ordin $3$, $aaabbb$, apare ca subsir in $A$, dar cea de ordin $4$ nu
* $ba$ - Bâlbâiala de ordin $4$ apare ca subsir in $A$, dar cea de ordin $5$, $bbbbbaaaaa$, nu
* $aba$ - Bâlbâiiala de ordin $3$, $aaabbbaaa$, apare ca subsir in $A$, dar cea de ordin $4$ nu

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