K. Consistent Occurrences
time limit per test
4 s
memory limit per test
256 mebibytes
input
standard input
output
standard output

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.

Input

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.

Output

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

Example
Input
6 4
aaaaaa
a
aa
aaa
aaaa
Output
6
3
2
1