勇者的后缀

题目限制

3000 ms 512 M

题目描述

勇者的名字是一个只包含小写英文字母的字符串 $S$。

魔王问勇者：你的名字中，以第 $i$ 个位置为起点的后缀，和起点位置在 $[l,r]$ 内的所有后缀的最长公共前缀的长度是多少？

勇者答了出来。

但魔王逼问勇者再答出达到这个最长值的后缀的起点是 $[l,r]$ 中的哪一个。如有多个解，魔王要求这个后缀的字典序最小。

勇者慌了。

他答出了一个，魔王又问一个；答出两个，魔王又问一个……魔王一共问了 $m$ 个这样的问题。

请你帮勇者回答魔王的问题。

输入格式

第一行，一个仅包含小写英文字母的字符串 S，表示勇者的名字。 第二行，一个正整数 m，表示问题的个数。 以下 m 行，每行三个正整数 i, l, r，表示魔王的一个问题。 其中1≤m,|S|≤2e5。

输出格式

对于魔王的每个问题，输出一行两个正整数，分别表示最长公共前缀的长度和达到这个最长值的后缀的起点。

数据范围

对于 20% 的数据，$m = 1$；

对于 50% 的数据，$m, |S| \le 10^3$；

对于 100% 的数据，$1 \le m, |S| \le 2 \times 10^5, 1 \le i \le |S|, 1 \le l \le r \le |S|$。

输入样例

abcbcd
3
1 2 4
2 2 5
2 3 6

输出样例

0 2
5 2
2 4

样例解释

对于第一个问题，以 $1$ 为起点的后缀为 $\texttt{abcbcd}$，所有起点在 $[2,4]$ 内的后缀为 $\{\texttt{bcbcd},\texttt{cbcd},\texttt{bcd}\}$，显然不存在任何公共前缀，故最长值为 $0$，而字典序最小的为 $\texttt{bcbcd}$。

对于第二个问题，以 $2$ 为起点的后缀为 $\texttt{bcbcd}$，所有起点在 $[2,5]$ 内的后缀为 $\{\texttt{bcbcd},\texttt{cbcd},\texttt{bcd},\texttt{cd}\}$，其中 $\texttt{bcbcd}$ 与其自身的最长公共前缀长度为 $5$，是达到最长值的唯一方案。

对于第三个问题，以 $2$ 为起点的后缀为 $\texttt{bcbcd}$，所有起点在 $[3,6]$ 内的后缀为 $\{\texttt{cbcd},\texttt{bcd},\texttt{cd},\texttt{d}\}$，其中 $\texttt{bcbcd}$ 与 $\texttt{bcd}$ 的最长公共前缀长度为 $2$，是达到最长值的唯一方案。