409756: GYM103729 J Palindrome Reversion

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. Palindrome Reversiontime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input, they are fundamental tools for cryptography.

But the following is not:

Given a string $$$s$$$, can you reverse exactly an interval in $$$s$$$ and make $$$s$$$ a palindrome?

If you don't know what is palindrome and reversion, here is a brief definition:

A palindrome is a string which reads the same backward as forward.

And for a string $$$s = s_1s_2\dots s_{l-1}s_ls_{l+1}\dots s_{r-1}s_rs_{r+1}\dots s_n$$$,

we define $$$\mathrm{reverse}(s,l,r) = s_1s_2\dots s_{l-1}s_rs_{r-1}\dots s_{l+1}s_ls_{r+1}\dots s_n$$$

Input

One line contains a string $$$s$$$, consisting of lowercase English letters, it's guaranteed that $$$1 \le |s| \le 10^5$$$.

Output

Print "-1 -1" if there's no solution.

Otherwise output two integers $$$l,r\ (1\le l\le r\le |s|)$$$ in a line representing the interval. If there are multiple solutions, just output any of them.

ExamplesInput
bcbaa
Output
1 4
Input
ababaa
Output
3 6
Input
abcb
Output
-1 -1
Note

"bcbaa" $$$\to$$$ "abcba"

"ababaa" $$$\to$$$ "abaaba"

加入题单

上一题 下一题 算法标签: