#338. 基本子串字典

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