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 ti.
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 ≤ n ≤ 105, 1 ≤ m ≤ 105).
The second line contains the string s consisting of n lowercase English letters.
Each of the next m lines contains a single string ti consisting of lowercase English letters: the i-th query (1 ≤ |ti| ≤ n, where |ti| is the length of the string ti).
It is guaranteed that the total length of all ti does not exceed 105 characters.
For each query i, print one integer on a separate line: the maximum size of a consistent set of occurrences of ti in s.
6 4
aaaaaa
a
aa
aaa
aaaa
6
3
2
1
Name |
---|