Please note the special time limit for this problem.

Given a string $s$ of length $n$. The center of a substring $s[i \dots j]$ is defined as $\frac{i+j}{2}$.

You need to answer $q$ queries. Each query provides a value $k$, and you are asked to find the sum of the number of borders for all substrings whose center is $\frac{k}{2}$.

The definition of a border is as follows: a non-empty string $t$ is a border of another string $s$ if and only if $t$ is both a prefix and a suffix of $s$. For example, for any non-empty string $s$, $s$ itself is a border of $s$.

Input

Read from standard input.

The first line contains two positive integers $n$ ($1 \le n \le 10^6$) and $q$ ($1 \le q \le 20$), representing the length of the input string $s$ and the number of queries, respectively.

The second line contains a string $s$ of length $n$, consisting of lowercase English letters.

The next $q$ lines each contain an integer $k$ ($2 \le k \le 2n$), representing a query.

Output

Output to standard output.

Output $q$ lines, where the $i$-th line represents the answer to the $i$-th query.

Examples

Input 1

9 6
bbabbbbaa
2
5
10
11
14
15

Output 1

1
3
8
9
3
2

Note

When $k=2$, the only substring with center $k/2$ is $s[1 \dots 1] = b$, which has $1$ border.

When $k=5$, the substrings with center $k/2$ are $s[2 \dots 3] = ba$ and $s[1 \dots 4] = bbab$, which have $1$ and $2$ borders, respectively.

When $k=10$, the substrings with center $k/2$ are $s[5 \dots 5] = b$, $s[4 \dots 6] = bbb$, $s[3 \dots 7] = abbbb$, $s[2 \dots 8] = babbbba$, and $s[1 \dots 9] = bbabbbbaa$, which have $1, 3, 1, 2, 1$ borders, respectively.