若非空字符串 S,T 满足 T 既是 S 的前缀也是 S 的后缀,且 |T|<|S| ,则称 T 或 |T| 是 S 的border。
有一个字符串 S ,有 q 次询问,每次给定一个 S 的子串,询问这个串的最短border、最长border、border个数。
输入格式
第一行一个字符串 S。 第二行一个整数 q ,接下来 q 行每行两个数 l,r 表示询问 S[l⋯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×105