시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
4 초 512 MB 1 1 1 100.000%

문제

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$.

예제 입력 1

6 4
aaaaaa
a
aa
aaa
aaaa

예제 출력 1

6
3
2
1