Problem: You are given a string s of length n. Does a tree with n vertices that satisfies the following conditions exist?

* The vertices are numbered 1,2,..., n.
* The edges are numbered 1,2,..., n-1, and Edge i connects Vertex u_i and v_i.
* If the i-th character in s is `1`, we can have a connected component of size i by removing one edge from the tree.
* If the i-th character in s is `0`, we cannot have a connected component of size i by removing any one edge from the tree.



If such a tree exists, construct one such tree.

Constraints

* 2 \leq n \leq 10^5
* s is a string of length n consisting of `0` and `1`.

Input

Input is given from Standard Input in the following format:


s


Output

If a tree with n vertices that satisfies the conditions does not exist, print `-1`.

If a tree with n vertices that satisfies the conditions exist, print n-1 lines. The i-th line should contain u_i and v_i with a space in between. If there are multiple trees that satisfy the conditions, any such tree will be accepted.

Examples

Input

1111


Output

-1


Input

1110


Output

1 2
2 3
3 4


Input

1010


Output

1 2
1 3
1 4

Solution (in PYTHON3):

Solution:
x = [c  for c in input()]

n = len(x)
ret=[]
for i in range(n-1):
    ret.append([0,0])

if x[n-1] == "1":
    print (-1)
elif x[0] == "0":
    print (-1)
else:
    flg = 1
    for i in range(int((n-1)/2)):
        if x[i] != x[n-1-i-1]:
            flg = 0
    if flg == 0:
        print (-1)
    else:
        a=1
        b=n
        for i in range(int((n-2)/2)):
            if x[i] == "1":
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
                a=i+2
                b=n-i-2+1
            else:
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
                
        if n % 2 == 1:
            i = int((n-3)/2)
            if x[i] == "1":
                ret[i] = [a,i+2]
                ret[n-i-2] = [b,n-i-2+1]
            else:
                tmp = b
                for j in range(i):
                    if ret[n-j-2][1] == b:
                        ret[n-j-2][1] = a
                    if ret[n-j-2][0] == b:
                        ret[n-j-2][0] = a
                ret[i] = [a,i+2]
                ret[n-i-2] = [a,tmp]
        else:
            i = int(n/2)-1
            if x[i] == "1":
                ret[i] = [a,b]
            else:
                tmp = b
                for j in range(i):
                    if ret[n-j-2][1] == b:
                        ret[n-j-2][1] = a
                    if ret[n-j-2][0] == b:
                        ret[n-j-2][0] = a
                ret[i] = [a,b]
                
        
        for i in range(n-1):
            print ("{0} {1}".format(ret[i][0], ret[i][1]))