← 返回题目列表

AtCoder · ukuku09_d

D. 乌库库

中文机器翻译题面 查看原题

配点 : 100 点

問題文

有一天,库先生注意到自己的名字是一个奇数长度的回文。

乌库先生的长度 N 的字符串 S 拥有。

乌库先生 Q 一个连续的子字符串 S[L_i:R_i] 对于它,想求出最长奇数长度回文的长度。

请代替懒惰的乌库先生,编写程序求出它。

(15:24补充)要求的奇数长度回文也必须是连续的。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq Q \leq 10^5
  • S 由小写字母组成的长度 N 除
  • 1 \leq L_i \leq R_i \leq N

入力

输入是按以下格式从标准输入给出的。

N Q
S
L_1 R_1
:
L_Q R_Q

出力

输出是 由 Q 行组成。

i 线 i 个查询的答案。


入力例 1

10 3
ukunichiaa
1 10
1 3
9 10

出力例 1

3
3
1

请注意,“aa”不满足条件,因为我们正在寻找奇数回文的长度。


入力例 2

9 3
ababcbaba
1 5
1 7
1 9

出力例 2

3
5
9