Siri has discovered a magical symbol $S$, which can undergo two types of operations:

1. Clicking on a symbol $S$ will turn it into $0S1S$.
2. Clicking on a symbol $S$ will turn it into $1S0S$.

At any point, you can choose to make all symbols disappear, leaving only the $0$ and $1$ characters in the string. Now Siri wants to know if it is possible to obtain a given binary string $T$ through some sequence of operations.

Input

A single binary string $T$ ($1 \le |T| \le 10^6$).

Output

If a solution exists, output the number of operations $n$ ($1 \le n \le 10^6$) on the first line. Then output $n$ lines, each containing two space-separated integers $pos$ and $op$, representing that you perform operation $op$ on the $pos$-th symbol in the current string. Otherwise, output -1.

Examples

Input 1

0011

Output 1

2
1 1
1 1

Note

Explanation of the example: Initially $S$. First operation on 1, resulting in $0S1S$. Second operation on 1, resulting in $00S1S1S$. After the symbols $S$ disappear, we get $0011$.