Security Guard
Contest: Kotlin Heroes: Episode 9 (Unrated, T-Shirts + Prizes!)
Difficulty rating: 1600
Tags: *special, greedy

Monocarp is a security guard in Berland State University. Every day, he tracks how many people and at what time enter and leave the university. He writes this information down as follows:

- when someone enters the university, Monocarp writes a plus sign '+';
- when someone leaves the university, Monocarp writes a minus sign '-'.

At the beginning of the current day, there are no people at the university, except for Monocarp. During the day, Monocarp wrote out a sequence $$$s$$$. The characters in $$$s$$$ are listed in the order Monocarp wrote them.

Suddenly, Monocarp's boss decided to check his work. Unfortunately, Monocarp is a bit careless. So, the sequence $$$s$$$ that he wrote might be impossible. For example, the sequence "+--" can't happen, since it represents a scenario when one person enters the university and two leave.

Before his boss starts checking the sequence, Monocarp has the time to swap at most one pair of characters in it. Can he do it in such a way that the resulting sequence is plausible? Note that if the given sequence is already plausible, Monocarp doesn't have to swap anything.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains a single string $$$s$$$ ($$$1 \le |s| \le 3 \cdot 10^5$$$), consisting only of characters '+' and/or '-'. A plus sign '+' represents a person entering the university. A minus sign '-' represents a person leaving the university.

The sum of all $$$|s|$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output format:
For each test case, print an answer.

If it's impossible to swap at most one pair of characters so that the resulting sequence is plausible, print -1.

Otherwise, print two integers. If you swap one pair of characters, print two distinct integers from $$$1$$$ to $$$n$$$ — the indices of characters to swap. If you don't swap, print one integer from $$$1$$$ to $$$n$$$ twice — swap a character with itself.

If there are multiple answers, print any of them.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
6
-+
+-
+++-
---++
+
-

Example output:
1 2
1 1
1 1
-1
1 1
-1

Editorial:
If the sequence is already plausible, we don't have to swap anything. To check that, you can iterate over the characters of the string, and maintain some sort of balance — the number of plus signs minus the number of minus signs. Basically, keep track of how many people are currently inside. If all values are non-negative, the sequence is plausible. You can print "1 1", for example.
Otherwise, there exist positions, where the balance is negative. We'd want to fix them all. Consider what happens to the balances when two characters get swapped. If the characters are the same, nothing happens. So, we'd have to swap a plus with a minus. Consider the case with $$$s_i = $$$ '-', $$$s_j = $$$ '+' and $$$i < j$$$. Swapping them will increase all balances between $$$i$$$ and $$$j - 1$$$ by $$$2$$$. For $$$i > j$$$, the balances between $$$j$$$ and $$$i - 1$$$ will decrease by $$$2$$$.
Thus, it only makes sense to swap a minus with a plus that is to the right of it. Moreover, of all options, why not swap the leftmost minus with the rightmost plus? A segment of increasing balances for any other swap is included in the segment for that swap. Check for plausibility again and print the answer.
Overall complexity: $$$O(n)$$$ per testcase.