問題文

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

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

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

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

補足:

$1\le i\le r$ に対して $T[x-i]=T[x+i]$ が成り立ち ( ただし，$1\le x-r\le x+r\le 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$ である．

入力

$NKQ$
$S$
$A_1$
$A_2$
$:$
$A_Q$

• $S$ は英小文字からなる文字列
• $1\le N\le 2\times {10}^5$
• $1\le K\le {10}^9$
• $1\le Q\le 2\times {10}^5$
• $1\le A_i\le 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