Description

Bob 是一位有抱负的先锋派作家。他鄙视空格、标点符号、大写字母等的使用，因此他的故事只是一长串英文小写字母。评论家们还注意到，他的风格中有一种对重复的偏爱，也就是说，有时会出现同一个子串在他的故事中连续出现两次，中间没有其他字符插入。

Bob 向 $q$ 家不同的文学杂志投稿了他最新的杰作，这是一串长度为 $n$ 的字符串，希望至少有一家愿意发表。结果比他预想的还要好，所有 $q$ 家杂志的编辑都表示愿意发表他故事的一部分（即某个子串），但前提是他需要找出该部分中最长的重复（即某个较短的子串连续出现两次）。编辑们打算删除这部分，以避免故事过于无聊。现在 Bob 需要你的帮助来回答编辑们的这些问题。

请编写一个程序，给定一个长度为 $n$ 的字符串 $s[1]s[2]\ldots s[n]$，回答 $q$ 个查询。每个查询形式为“给定 $a_i$ 和 $b_i$，在 $s[a_i]s[a_i+1]\ldots s[b_i]$ 这个子串中，最长的字符串 $t$ 使得 $tt$ 作为子串出现的长度是多少？最左边的这样一个重复从哪里开始？”

Input Format

第一行包含两个整数 $n$ 和 $q$。
第二行包含长度为 $n$ 的字符串 $s$，所有字符均为英文小写字母。
接下来的 $q$ 行描述每个查询，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$，用空格分隔。

Output Format

输出 $q$ 行，每行包含两个用空格分隔的整数 $\ell_i$ 和 $c_i$。$\ell_i$ 表示在 $s[a_i]s[a_i+1]\ldots s[b_i]$ 中，最长的字符串 $t$ 使得 $tt$ 作为子串出现的长度，$c_i$ 表示最左边的这样一个重复的起始位置，即最小的整数满足 $a_i \leq c_i$，$c_i + 2\ell_i - 1 \leq b_i$ 且 $s[c_i]\ldots s[c_i+\ell_i-1] = s[c_i+\ell_i]\ldots s[c_i+2\ell_i-1]$。如果 $\ell_i = 0$，则定义 $c_i = a_i$。

10 4
cabaabaaca
4 8
1 9
5 9
8 10

1 4
3 2
1 7
0 8

Hint

说明

上面示例中的四个查询分别对应子串 $\textbf{\underline{a}abaa}$、$\textbf{c\underline{aba}abaac}$、$\textbf{ab\underline{a}ac}$ 和 $\textbf{aca}$；加粗部分是该查询结果所指的子串（长度为 $\ell_i$，起始于 $c_i$）。在最后一个查询中没有重复，因此 $\ell_4 = 0$。

输入范围

• $1 \leq n \leq 10^6$
• $1 \leq q \leq 100$
• 对于每个 $i = 1, 2, \ldots, q$，$1 \leq a_i \leq b_i \leq n$

由 ChatGPT 4.1 翻译