Computational Biology

Byteasar works at the Byteland Centre for Computational Biology. He has just received a long sequence of $n$ genomes and wants to find the cyclic fragments that occur most often in it.

The sequence is a word $s = s_1 s_2 \ldots s_n$ over capital English letters. A cyclic rotation of a word is obtained by moving its last letter to the front, possibly several times in a row. For example, ABAABA has three distinct cyclic rotations: ABAABA, BAABAA, and AABAAB. A word $u$ is a subword of a word $v$ if $u$ occurs in $v$ as a block of consecutive letters.

A word $t$ is a cyclic fragment of $s$ if every cyclic rotation of $t$ is a subword of $s$. For such a $t$, its number of cyclic occurrences in $s$ is the total number of occurrences in $s$ of the distinct cyclic rotations of $t$.

For each query length $m$, report the largest number of cyclic occurrences achievable by a cyclic fragment of $s$ of length $m$. If $s$ has no cyclic fragment of length $m$, the answer is 0.

The first line contains two integers $n$ and $q$ ($2 \le n \le 500{,}000$, $1 \le q \le 8$): the length of the genome sequence and the number of queries. The second line contains the word $s$, made of $n$ capital letters of the English alphabet. Each of the next $q$ lines contains one integer $m_i$ ($2 \le m_i \le n$), the length of the cyclic fragments to consider in that query.

Output $q$ lines. The $i$-th line must contain a single integer: the maximum number of cyclic occurrences over all cyclic fragments of $s$ of length $m_i$ (or 0 if none exists).

Take $s =$ AABAABACDABAABAA. For length 6, the cyclic fragment AABAAB has three distinct cyclic rotations, and together they occur 4 times in $s$: once as AABAAB, twice as ABAABA, and once as BAABAA. No length-6 cyclic fragment does better, so the answer is 4. For length 3, the cyclic fragment AAB occurs 10 times in total across its rotations AAB, ABA, and BAA, which is the maximum.