Beautiful Binary String Transformation

Two friends, K and M, wrote a binary string \(S\) whose ending contains two consecutive spaces (represented by a dot . in the input). M calls a binary string beautiful if and only if there is no inversion – that is, there is no occurrence of a digit \(1\) that appears before a digit \(0\) when reading the non‐space characters from left to right (so the non–space part must be in non–decreasing order, namely all \(0\)s followed by all \(1\)s).

To meet M’s requirement, K is allowed to perform the following modification repeatedly (at most 10000 moves):

In one move, K can choose two consecutive non–space characters in the string and remove them from their current positions; then he selects two consecutive empty positions (a pair of spaces) in the string and inserts the two characters there without changing their relative order. As a result, the positions that previously held the two characters become spaces, and the two empty positions are replaced by the moved characters.

You are to determine a sequence of moves (not necessarily minimum) that transforms \(S\) into a beautiful binary string. The final positions of the spaces do not matter. If it is impossible to obtain a beautiful string or if it requires more than 10000 moves, output -1.

Note: The input string in its initial form always has two trailing spaces (displayed as . in the input) and only the characters \(0\) and \(1\) appear apart from these trailing spaces.

Input/Output details of a valid solution: The solution should output first the number of moves used, and then for each move output two integers. In each move, the two integers represent (in 0–indexed order relative to the current non–space sequence) the starting index of the removed pair and the insertion position where that same pair is inserted in the new order. (Any valid sequence of moves that achieves the transformation is accepted.)

inputFormat

The input consists of a single line containing a string \(S\). In \(S\), digits \(0\) and \(1\) represent themselves, and a dot . represents a space. It is guaranteed that the ending of \(S\) contains exactly two consecutive dots, representing two spaces.

outputFormat

If it is possible to transform \(S\) into a beautiful binary string within 10000 moves, first output the number of moves \(k\) (\(0 \le k \le 10000\)) on a line, followed by \(k\) lines each containing two integers separated by a space representing the move. If the transformation is impossible or requires more than 10000 moves, simply output -1.

Note: The move format is as follows: if at a given step the non–space sequence is considered as an array (0-indexed), you choose a pair starting at index i (i.e. positions \(i\) and \(i+1\)) and then insert that pair at position j in the remaining sequence (positions are counted after removal of the pair). Any valid move sequence is accepted.

sample

0011..

0