E - Genni Nge!
Earlgray
2
s
1024
MB
100
点
問題文
英小文字からなる文字列 $S$ が与えられます。 $|S|$ で $S$ の長さを表します。以下のクエリを $Q$ 個処理してください。
- $2$ つの整数 $l$ , $r$ ($1 \leq l \leq r \leq |S|$) が与えられます。 $S$ の $l$ 番目から $r$ 番目までの文字からなる部分文字列について、末尾に最小何文字加えると回文にできるか答えてください。
制約
- $S$ は英小文字からなる文字列
- $S$ の長さは $1$ 以上 $200{,}000$ 以下である
- $Q$ は整数で、 $1 \leq Q \leq 200{,}000$
- $l$ , $r$ は整数で、 $1\leq l\leq r \leq |S|$
入力
$S$
$Q$
$\mathrm{Query} _ 1$
$\mathrm{Query} _ 2$
$\vdots$
$\mathrm{Query} _ Q$
$\mathrm{Query} _ i$ ($1\leq i\leq Q$) は $i$ 番目のクエリを表します。 $\mathrm{Query} _ i$ は次の形式で与えられます。
$l$ $r$
出力
各クエリに対する答えとなる整数を、順に、改行区切りで出力してください。
入力例 1
aaabba
3
1 6
1 3
4 6
出力例 1
2
0
2
$1$ 番目のクエリでは、 $S$ の部分文字列 aaabba の末尾に最小で $2$ 文字加えて回文 aaabbaaa を得られるので、 $2$ を出力しなければなりません。
$2$ 番目のクエリでは、 $S$ の部分文字列 aaa の末尾に最小で $0$ 文字加えて回文 aaa を得られるので、 $0$ を出力しなければなりません。
$3$ 番目のクエリでは、 $S$ の部分文字列 bba の末尾に最小で $2$ 文字加えて回文 bbabb を得られるので、 $2$ を出力しなければなりません。