配点 : 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