题目背景

$\ulcorner$ 運命は、人間を弄ぶものではありません，それは、人間自身が選び取る道なのです。$\lrcorner$

$\ulcorner$ 命运不是玩弄人类的工具，它是人类自己选择的道路。$\lrcorner$

愿，人生不是回文的，我们的经历亦不曾是别人前缀。

题目描述

给定一个长度为 $n$ 的由小写字母构成的字符串 $S$，以及 $q$ 个询问。

对于每个询问，给定一个 $len_1$ 和 一个 $len_2$，其中 $len_1 \lt len_2$，求一对 $S$ 的回文子串 $S_1,S_2$。

需满足以下要求：

• $|S_1|=len_1$。
• $|S_2|=len_2$。
• $S_1$ 是 $S_2$ 的前缀且 $S_1$ 与 $S_2$ 的第一个字符在 $S$ 中位置相同。

你只需要输出 $S_1$ 第一个字母在 $S$ 中的位置即可。

如果不存在请输出 $-1$，如果有多组答案输出 $S_1$ 最靠前的一组。

输入格式

第一行，两个整数 $n,q$，表示字符串长度和询问的个数。

第二行，一个由小写字母构成的字符串 $S$。

接下来 $q$ 行，一行两个整数 $len_1,len_2$，意义如上。

输出格式

共 $q$ 行，每行一个整数表示一组询问的答案。

5 3
ababa
1 2
1 5
3 5

-1
1
1

提示

数据范围

对于全部的数据：$1\le n,q\leq5\times 10^5,1 \le len_1 \lt len_2 \le n$，保证询问随机生成，不保证字符串随机生成，详细数据范围见下表。 | Subtask 编号 | 特殊限制 | 分值 | | :--------: | :--------: | :--: | |#0|$n,q\leq 10$|$10$| |#1|$n,q\leq 1000$|$20$| |#2|$n,q\leq 10^5$|$30$| |#3|$n,q\leq 5\times 10^5$|$40$|