Монокарп работает охранником в Берляндском Государственном Университете. Каждый день он отслеживает, сколько людей и в какое время входят и выходят из университета. Он записывает эту информацию следующим образом:
- когда кто-то входит в университет, Монокарп пишет знак плюса «+»;
- когда кто-то покидает университет, Монокарп пишет знак минуса «-».
В начале текущего дня в университете нет людей, кроме Монокарпа. В течение дня Монокарп записал последовательность \(s\). Символы в \(s\) перечислены в том порядке, в котором Монокарп их записал.
Внезапно начальник Монокарпа решил проверить его работу. К сожалению, Монокарп немного небрежен. Поэтому записанная им последовательность \(s\) может быть невозможной. Например, последовательность «+--» не может произойти, так как она представляет сценарий, когда один человек входит в университет, а выходят двое.
Прежде чем его начальник начнет проверять последовательность, у Монокарпа есть время поменять местами максимум одну пару символов в ней. Может ли он сделать это таким образом, чтобы результирующая последовательность была правдоподобной? Обратите внимание, что если данная последовательность уже правдоподобна, Монокарпу не нужно ничего менять.
Выходные данные
Для каждого набора входных данных выведите ответ.
Если невозможно поменять местами максимум одну пару символов так, чтобы результирующая последовательность была правдоподобной, выведите -1.
В противном случае выведите два целых числа. Если вы меняете местами одну пару символов, выведите два различных целых числа от \(1\) до \(n\) — индексы символов для обмена. Если вы не меняете местами, выведите одно и то же целое число от \(1\) до \(n\) дважды — поменяйте символ сам с собой.
Если есть несколько ответов, выведите любой из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
-+
+-
+++-
---++
+
-
|
1 2
1 1
1 1
-1
1 1
-1
|