310923: CF1910B. Security Guard

B. Security Guardtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

6
-+
+-
+++-
---++
+
-

Output

1 2
1 1
1 1
-1
1 1
-1

题目大意：
单选题。莫诺卡普是伯兰国立大学的一名保安。每天，他都记录有多少人在何时进入和离开大学。他以以下方式记录这些信息：
- 当有人进入大学时，莫诺卡普写一个加号 '+';
- 当有人离开大学时，莫诺卡普写一个减号 '-'。
在当前天的开始，除了莫诺卡普之外，大学里没有人。在这一天期间，莫诺卡普写出了一个序列 s。序列 s 中的字符按照莫诺卡普写的顺序列出。
突然，莫诺卡普的老板决定检查他的工作。不幸的是，莫诺卡普有点粗心。所以，他写的序列 s 可能是不可能的。例如，序列 "++-" 是不可能的，因为它表示一个人进入大学而两个人离开的场景。
在老板开始检查序列之前，莫诺卡普有时间至多交换序列中的一对字符。他能否以这种方式使得结果序列是合理的？注意，如果给定的序列已经合理，莫诺卡普不需要交换任何东西。

输入数据格式：
第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。
每个测试用例的唯一一行包含一个字符串 s (1 ≤ |s| ≤ 3 × 10^5)，仅由字符 '+' 和/or '-' 组成。加号 '+' 表示一个人进入大学。减号 '-' 表示一个人离开大学。
所有测试用例的 |s| 之和不超过 3 × 10^5。

输出数据格式：
对于每个测试用例，输出一个答案。
如果不可能通过交换至多一对字符使得结果序列是合理的，输出 -1。
否则，输出两个整数。如果你交换了一对字符，输出两个不同的整数从 1 到 n —— 要交换的字符的索引。如果你没有交换，输出一个整数从 1 到 n 两次 —— 将一个字符与它自己交换。
如果有多个答案，输出其中任何一个。题目大意： 单选题。莫诺卡普是伯兰国立大学的一名保安。每天，他都记录有多少人在何时进入和离开大学。他以以下方式记录这些信息： - 当有人进入大学时，莫诺卡普写一个加号 '+'; - 当有人离开大学时，莫诺卡普写一个减号 '-'。 在当前天的开始，除了莫诺卡普之外，大学里没有人。在这一天期间，莫诺卡普写出了一个序列 s。序列 s 中的字符按照莫诺卡普写的顺序列出。 突然，莫诺卡普的老板决定检查他的工作。不幸的是，莫诺卡普有点粗心。所以，他写的序列 s 可能是不可能的。例如，序列 "++-" 是不可能的，因为它表示一个人进入大学而两个人离开的场景。 在老板开始检查序列之前，莫诺卡普有时间至多交换序列中的一对字符。他能否以这种方式使得结果序列是合理的？注意，如果给定的序列已经合理，莫诺卡普不需要交换任何东西。 输入数据格式： 第一行包含一个整数 t (1 ≤ t ≤ 10^4) —— 测试用例的数量。 每个测试用例的唯一一行包含一个字符串 s (1 ≤ |s| ≤ 3 × 10^5)，仅由字符 '+' 和/or '-' 组成。加号 '+' 表示一个人进入大学。减号 '-' 表示一个人离开大学。 所有测试用例的 |s| 之和不超过 3 × 10^5。 输出数据格式： 对于每个测试用例，输出一个答案。 如果不可能通过交换至多一对字符使得结果序列是合理的，输出 -1。 否则，输出两个整数。如果你交换了一对字符，输出两个不同的整数从 1 到 n —— 要交换的字符的索引。如果你没有交换，输出一个整数从 1 到 n 两次 —— 将一个字符与它自己交换。 如果有多个答案，输出其中任何一个。