若非空字符串 $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}$ ) : 无特殊限制