Consistent Occurrences

Time limit4sMemory limit512 MB

Summary

Given a string s and many query strings, for each query find the largest set of non-overlapping occurrences of that query string in s.

Level: Hard8 of 10
Topics: String, String matching, Greedy, Sorting
Solved: No attempts yet

Problem

A consistent set of occurrences of string $t$ in string $s$ is 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$ .

Input

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.

Output

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

Examples1

Example 1
Input
```
6 4
aaaaaa
a
aa
aaa
aaaa
```
Expected output
```
6
3
2
1
```