問題文
N 文字の英小文字のみからなる文字列 S があります。Q 個のクエリが与えられるので、処理してください。
各クエリでは、整数 Li,Ri(1≤Li≤Ri≤N) が与えられるので、S の Li 文字目から Ri 文字目まで (両端含む) からなる部分文字列を Ti としたとき、Ti の部分文字列で回文であるものの長さの最大値を求めてください。
制約
- N,Q,Li,Ri は整数
- S は英小文字のみからなる
- S の長さは N
- 1≤N≤200000
- 1≤Q≤200000
- 1≤Li≤Ri≤N (1≤i≤Q)
入力
入力は以下の形式で標準入力から与えられます。
N
S
Q
L1 R1
L2 R2
⋮
LQ RQ
出力
Q 行出力せよ。
i 行目には、i 番目のクエリに対する答えを出力せよ。
サンプル
入力1
7
abbabba
7
1 3
2 5
3 5
1 4
4 7
2 6
1 7