#338. 基本子串字典

题目类型:传统型 时间限制:6000 ms 空间限制:512 MiB
输入文件:标准输入 输出文件:标准输出 答案检查器:文本比较

若非空字符串 $S,T$ 满足 $T$ 既是 $S$ 的前缀也是 $S$ 的后缀,且 $|T|<|S|$ ,则称 $T$ 或 $|T|$ 是 $S$ 的border。

有一个字符串 $S$ ,有 $q$ 次询问,每次给定一个 $S$ 的子串,询问这个串的最短border、最长border、border个数。


Input

第一行一个字符串 $S$。 第二行一个整数 $q$ ,接下来 $q$ 行每行两个数 $l,r$ 表示询问 $S[l...r]$ 这个子串,从零开始编号


Output

对每个询问输出一行。若没有border,则输出 $-1$ ,否则输出三个数表示最短border、最长border、border个数。


Sample Input 1

abacaba
2
0 6
1 2

Sample Output 1

1 3 2
-1

Sample Input 2

aaaaaa
1
0 5

Sample Output 2

1 5 5

Constraints

$|S|,\ q\leq 2\times10^5$

子任务 $1$ ( $\texttt{1pts}$ ) : $|S|,\ q\leq 2000$

子任务 $2$ ( $\texttt{38pts}$ ) : $|S|,\ q\leq 50000$

子任务 $3$ ( $\texttt{61pts}$ ) : 无特殊限制