問題文

長さ $N$ の文字列 $S$ と整数 $K$ が与えられます．

$S$ を $K$ 個連結して得られる文字列を $T$ とします．

$Q$ 個の以下のクエリが与えられるので処理してください．

• $T$ の $A_i$ 番目の文字を中心位置とする極大回文の長さを求めてください．

補足:

$1\leq i\leq r$ に対して $T[x - i] = T[x + i]$ が成り立ち ( ただし，$1\leq x - r \leq x + r\leq KN$ ) ，

$T[x - r - 1] \ne T[x + r + 1]$ または $x - r = 1$ または $x + r = KN$ が成り立つとき，

$T[x - r..x + r]$ を $T$ の $x$ 番目の文字を中心位置とする極大回文といい，その長さは $2r + 1$ である．

入力

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

• $S$ は英小文字からなる文字列
• $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$ は整数

出力

各クエリに対し，答えを 1 行に出力してください。

サンプル

17 2 2
ushitapunichiakun
17
34

3
1

13 3 3
abcdefgfedcba
7
20
33

13
39
13