Дана строка \(s\), состоящая из \(n\) букв, каждая буква — либо 'a', либо 'b'. Буквы в строке пронумерованы от \(1\) до \(n\).
\(s[l; r]\) — это подстрока подряд идущих букв с позиции \(l\) до позиции \(r\) строки включительно.
Строка называется сбалансированной, если количество букв 'a' в ней равно количеству букв 'b'. Например, строки «baba» и «aabbab» сбалансированные, а строки «aaab» и «b» — нет.
Найдите любую непустую сбалансированную подстроку \(s[l; r]\) строки \(s\). Выведите ее \(l\) и \(r\) (\(1 \le l \le r \le n\)). Если таких подстрок нет, то выведите \(-1\) \(-1\).
Выходные данные
На каждый набор входных данных выведите два целых числа. Если существует непустая сбалансированная подстрока \(s[l; r]\), то выведите \(l\) \(r\) (\(1 \le l \le r \le n\)). В противном случае выведите \(-1\) \(-1\).
Примечание
В первом наборе входных данных нет непустых сбалансированных подстрок.
Во втором и в третьем наборах входных данных есть несколько сбалансированных подстрок, включая всю строку «abbaba» и подстроку «baba».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
1
a
6
abbaba
6
abbaba
9
babbabbaa
|
-1 -1
1 6
3 6
2 5
|