Byteasar works in Byteland Centre for Computational Biology. He has just received a long sequence of $n$ genomes. His task is to find frequently occurring cyclic fragments of this sequence.

Byteasar's sequence can be represented as a word $s = s_{1}\ldots s_{n}$ of capital English letters. A cyclic fragment of s is a word t such that all its cyclic rotations^{1} are subwords of $s$.

Byteasar is interested in cyclic fragments of a given length $m$. For a given cyclic fragment $t$ of $s$, we define the number of cyclic occurrences of $t$ in $s$ as the total number of occurrences of distinct cyclic rotations of $t$ within $s$. Byteasar wants to find a cyclic fragment of length $m$ of the word s that has the largest number of cyclic occurrences. Please, write a program to help him.

^{1}A cyclic rotation of a word is constructed by moving its last letter to its beginning (possibly multiple times). For example, there are three different cyclic rotations of ABAABA, namely ABAABA, BAABAA and AABAAB. A word $u$ is a subword of $v$, if $u$ is a subsequence of $v$ consisting of several consecutive letters of $v$.

Input Format

The first line of the input contains two integers $n$ and $q$ ($2 ≤ n ≤ 500\,000$, $1 ≤ q ≤ 8$) which denote the length of the sequence of genomes and the number of queries to answer. The second line contains a word s composed of $n$ capital letters of the English alphabet. The following $q$ lines contain numbers $m_{i}$ ($2 ≤ m_{i} ≤ n$) defining the length of the cyclic fragments to consider.

Output Format

Your program should output $q$ lines. The $i$-th line should contain one integer denoting the maximal number of cyclic occurrences of any $m_{i}$-letter cyclic fragment of $s$.

Example

Input

16 2
AABAABACDABAABAA
6
3

Output

4
10

Notes

The cyclic fragment AABAAB occurs in the given word 4 times: once as AABAAB, twice as ABAABA and once as BAABAA. The cyclic fragment AAB occurs in this word 10 times.