P12671 「TFXOI Round 2」String
题目背景
$\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$ 最靠前的一组。
输入格式
无
输出格式
无
说明/提示
### 数据范围
对于全部的数据：$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$|