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

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

输入格式

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

输出格式

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

样例数据

样例 1 输入

abacaba
2
0 6
1 2

样例 1 输出

1 3 2
-1

样例 2 输入

aaaaaa
1
0 5

样例 2 输出

1 5 5

子任务

$|S|, q≤2×10^5$