19334번 - Consistent Occurrences 다국어

문제

Let us define a consistent set of occurrences of string $t$ in string $s$ as a set of occurrences of $t$ in $s$ such that no two occurrences intersect (in other words, no character position in $s$ belongs to two different occurrences).

You are given a string $s$ consisting of $n$ lowercase English letters, and $m$ queries. Each query contains a single string $t_i$.

For each query, print the maximum size of a consistent set of occurrences of $t$ in $s$.

입력

The first line contains two space-separated integers $n$ and $m$: the length of string $s$ and the number of queries (1ドル \le n \le 10^{5},ドル 1ドル \le m \le 10^{5}$).

The second line contains the string $s$ consisting of $n$ lowercase English letters.

Each of the next $m$ lines contains a single string $t_i$ consisting of lowercase English letters: the $i$-th query (1ドル \le |t_i| \le n,ドル where $|t_i|$ is the length of the string $t_i$).

It is guaranteed that the total length of all $t_i$ does not exceed 10ドル^{5}$ characters.

출력

For each query $i,ドル print one integer on a separate line: the maximum size of a consistent set of occurrences of $t_i$ in $s$.

제한

힌트