Stone_Enthusiast (OOI qualification)
Time limit: 2 seconds | Memory limit: 512 MB | Task type: batch
Algorithms: precomputation, greedy, binary search, string

# Stone Enthusiast

| Input file:   | standard input  |
| :------------- | :------------- |
| Output file:  | standard output |
| Time limit:   | 2 seconds       |
| Memory limit: | 512 megabytes   |

Once there was a boy who loved stones very much, so he could spend whole years studying them. Over these long years, he realized that each stone has a type, denoted by a letter of the Latin alphabet. The boy believes that everyone should know about stones, so he works in a museum where he showcases them.

In the museum, there are $n$ exhibits of stones arranged in the order specified by the string $s$, where the stone at the $i$-th stand is of type $s_i$. $m$ visitors have come to the boy, and each visitor wants to see only certain stones, the types of which are specified by the string $t$. The boy will guide the visitor through the stands in order from 1 to $n$, and at each stand, he can choose to either show the stone at that stand to the visitor or skip it. The boy must fulfill the visitor's wish, but he wants to make the stone viewing as challenging as possible.

Let's say the boy shows the stands with numbers $1 \le i_1 < i_2 < \dots < i_k \le n$, then these stones, in the order shown, must form the string $t$. In other words, it must hold that $k = |t|$, and for all $1 \le j \le k$, it must hold that $s_{i_j} = t_j$. The difficulty of the viewing is defined as the minimum distance between adjacent shown stands, that is, $\min(i_2 - i_1, i_3 - i_2, ..., i_k - i_{k-1})$. If it is impossible to choose such $k$ stands, then the viewing is considered impossible; otherwise, the boy will choose the viewing with the maximum possible difficulty.

Determine for each visitor whether their viewing is possible, and if so, what the maximum difficulty of viewing the stones could be.

### Input

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 200\,000$)—the number of exhibits in the museum and the number of visitors.

The second line contains the string $s$ of length $n$, consisting of lowercase Latin letters—the types of stones on the exhibits in the museum.

The following $m$ lines describe the visitors. The $i$-th line contains the string $t_i$, consisting of lowercase Latin letters ($2 \le |t_i| \le 200\,000$)—the types of stones that visitor $i$ wants to see.

It is guaranteed that the sum of all $|t_i|$ does not exceed $400\,000$.

### Output

For each of the $m$ visitors, output the maximum difficulty of the tour on a separate line, or $-1$ if the tour is impossible.

### Examples

| standard input | standard output |
| :------------- | :------------- |
| 7 3            | 6               |
| abacaba        |                 |
| aa             | 2               |
| acb            | 5               |
| ba             |                 |
| 12 2           |                 |
| openolympiad   | 4               |
| oli            | -1              |
| goal           |                 |
| 8 5            |                 |
| abbaabba       | 2               |
| bab            | 2               |
| baba           | 1               |
| bbbb           | 1               |
| aaaa           | 1               |
| abbaabba       |                 |

### Note

Consider the first example.

For the first visitor, it is optimal to choose the stands with numbers $[1, 7]$, then the difficulty of the viewing will be $7 - 1 = 6$.

For the second visitor, it is optimal to choose the stands with numbers $[1, 4, 6]$, then the difficulty of the viewing will be $\min(4 - 1, 6 - 4) = 2$.

For the third visitor, it is optimal to choose the stands with numbers $[2, 7]$, then the difficulty of the viewing will be $7 - 2 = 5$.

### Scoring

The tests for this problem consist of seven groups. Points for each group are awarded only if all tests of the group and all tests of some of the previous groups are passed. Note that passing the samples is not required for some groups.

Let $T$ denote the total length of all strings $t$.

| Group | Points | Additional constraints |   |   | Required groups | Comment                                     |
| :---- | :----- | :--------------------- | :- | :- | :-------------- | :------------------------------------------ |
|       |        | $n$                     | $m$ | $T$ |                 |                                             |
| 0     | 0      | –                       | –   | –   | –               | Samples.                                    |
| 1     | 16     | $n \le 20$            | –   | $T \le 1000$ | 0               |                                             |
| 2     | 14     | $n \le 500$            | –   | $T \le 500$  | 0               |                                             |
| 3     | 12     | –                       | –   | –   | –               | $s$ and $t$ consist only of the letter 'a'      |
| 4     | 16     | –                       | $m = 1$ | –   | –               | $s$ and $t$ consist only of letters 'a' and 'b' |
| 5     | 11     | –                       | $m = 1$ | –   | 4               |                                             |
| 6     | 17     | –                       | –   | –   | 3, 4            | $s$ and $t$ consist only of letters 'a' and 'b' |
| 7     | 14     | –                       | –   | –   | 0 – 6           |                                             |

Starter code:

Grader code:

Setup script:

Evaluation script: