Problem Statement

You are given a string $S$ of length $N$ and an integer $K$.

Let $T$ be the string obtained by concatenating $K$ copies of $S$.

You are given $Q$ queries of the following form, so process them.

• Find the length of the maximal palindrome centered at the $A_i$-th character of $T$.

Note:

If $T[x - i] = T[x + i]$ holds for $1\leq i\leq r$ (where $1\leq x - r \leq x + r\leq KN$), and

$T[x - r - 1] \ne T[x + r + 1]$ or $x - r = 1$ or $x + r = KN$ holds,

then $T[x - r..x + r]$ is called the maximal palindrome centered at the $x$-th character of $T$, and its length is $2r + 1$.

Input

$N\ K\ Q$
$S$
$A_1$
$A_2$
$:$
$A_Q$

• $S$ is a string consisting of lowercase English letters
• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq A_i \leq KN$
• $N, K, Q, A_i$ are integers

Output

For each query, output the answer on one line.

Sample

17 2 2
ushitapunichiakun
17
34

3
1

13 3 3
abcdefgfedcba
7
20
33

13
39
13