设 s 为长度等于 n 的字符串。它的字符编号从0到n-1,i和j是整数,0≤i<j<n。我们将函数 f 定义如下:
f(s, i, j) = s[i + 1... j - 1] + r(s[j... n - 1]) + r(s[0... i])。
这里 s[p...q] 是字符串 s 的一个子串,从位置 p 开始,到位置 q 结束(含); “+”是字符串连接运算符; r(x) 是以相反顺序写入 x 字符串的字符而得到的字符串。如果 j = i + 1,则子串 s[i + 1... j - 1] 被视为空。
给定两个字符串 a 和 b。找到 i 和 j 的值,使得 f(a, i, j) = b。 i 的数量应该是最大可能的。如果对于这个 i 存在多个有效的 j 值,则选择最小的 j。
输入
前两行输入分别为非空字符串 a 和 b。每个字符串的长度不超过 106 个字符。字符串可以包含 ASCII 代码从 32 到 126(含)的任何字符。
输出
打印两个整数 i, j — 问题的答案。如果不存在解,则打印“-1 -1”(不带引号)。
示例
输入 #1
Die Polizei untersucht eine Straftat im IT-Bereich. untersucht eine Straftat.hciereB-TI mi ieziloP eiD
输出 #1
11 36
输入 #2
cbaaaa aaaabc
输出 #2
4 5
输入 #3
123342 3324212
输出 #3
-1 -1