Purple rain falls in the magic kingdom of Linearland
which is a straight, thin peninsula.
On close observation however, Prof. Nelson Rogers finds that
actually it is a mix of Red and Blue drops.
In his zeal, he records the location and color of the
raindrops in different locations along the peninsula. Looking
at the data, Professor Rogers wants to know which part of
Linearland had the “least” purple rain.
After some thought, he decides to model this problem as
follows. Divide the peninsula into $n$ sections and number them West to
East from $1$ to
$n$. Then, describe the
raindrops as a sequence of R and B, depending on whether the rainfall in each section
is primarily red or blue. Finally, find a subsequence of where
the difference between the number of R and
the number of B is maximized.
The input consists of a single line containing a string of
($1 \le n \le 10^5$),
describing the color of the raindrops in sections $1$ to $n$.
It is guaranteed that the string consists of uppercase ASCII
letters ‘R’ and ‘B’
Print, on a single line, two space-separated integers that
describe the starting and ending positions of the part of
Linearland that had the least purple rain.
If there are multiple possible answers, print the one that
has the Westernmost (smallest-numbered) starting section. If
there are multiple answers with the same Westernmost starting
section, print the one with the Westernmost ending section.
|Sample Input 1
||Sample Output 1
|Sample Input 2
||Sample Output 2