Welcome to ZOJ
 Problem Sets Information Select Problem Runs Ranklist
ZOJ Problem Set - 4079
Hello, Hello and Hello

Time Limit: 6 Seconds      Memory Limit: 131072 KB      Special Judge

A ternary string is a sequence of digits, where each digit is either $0$, $1$, or $2$.

Chiaki has a nonempty ternary string $s$. Initially, the characters are sorted in non-decreasing order (i.e. all $0$s appear before all $1$s and all $1$s appear before all $2$s). Chiaki would like to shuffle the characters such that no two consecutive characters have the same value using the following operation: choose two integers $l$ and $r$ ($l \le r$), take characters from position $l$ to position $r$ inclusively, and move them to the end of the string.

Chiaki would like to know the minimum number of operations needed.

#### Input

There are multiple test cases. The first line of input is an integer $T$ indicates the number of test cases. For each test case:

The first line contains a ternary string $s$ ($1 \le |s| \le 10^6$).

It is guaranteed that the sum of all $|s|$ does not exceed $10^6$.

#### Output

For each test case, output "-1" (without the quotes) if Chiaki can not shuffle the string using the operations described above. Otherwise, output an integer $k$ in the first line -- the minimum number of operations needed. Each of the next $k$ lines output two integers $l$ and $r$ -- denoting an operation.

#### Sample Input

2
001122
000022


#### Sample Output

2
4 5
1 1
-1


Author: LIN, Xi
Source: Yet Another Xi Lin Contest
Submit    Status