U142356 勇者的后缀

勇者的名字是一个只包含小写英文字母的字符串 S 。 魔王问勇者：你的名字中，以第 i 个位置为起点的后缀，和起点位置在 [l, r] 内的所有后缀的最长公共前缀的长度是 多少？ 勇者答了出来。 但魔王逼问勇者再答出达到这个最长值的后缀的起点是 [l, r] 中的哪一个。如有多个解，魔王要求这个后缀的字典序 最小。 勇者慌了。 他答出了一个，魔王又问一个；答出两个，魔王又问一个……魔王一共问了 m 个这样的问题。 请你帮勇者回答魔王的问题。

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

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

### 数据范围 对于 20% 的数据，m = 1； 对于 50% 的数据，m, |S| ≤ 10^3； 对于 100% 的数据，1 ≤ |S|, m ≤ 2 × 10^5, 1 ≤ i ≤ |S|,1 ≤ l ≤ r ≤ |S| 。 ### 样例解释 对于第一个问题，以 1 为起点的后缀为 abcbcd ，所有起点在 [2,4] 内的后缀为 {bcbcd,cbcd,bcd} ，显然不 存在任何公共前缀，故最长值为 0 ，而字典序最小的为 bcbcd 。 对于第二个问题，以 2 为起点的后缀为 bcbcd ，所有起点在 [2,5] 内的后缀为 {bcbcd,cbcd,bcd,cd} ，其 中 bcbcd 与其自身的最长公共前缀长度为 5 ，是达到最长值的唯一方案。 对于第三个问题，以 2 为起点的后缀为 bcbcd ，所有起点在 [3,6] 内的后缀为 {cbcd,bcd,cd,d} ，其中 bcbcd 与 bcd 的最长公共前缀长度为 2 ，是达到最长值的唯一方案。