To improve the boomerang throwing skills of the animals, Zookeeper has set up an $n \times n$ grid with some targets, where each row and each column has at most $2$ targets each. The rows are numbered from $1$ to $n$ from top to bottom, and the columns are numbered from $1$ to $n$ from left to right. 

 For each column, Zookeeper will throw a boomerang from the bottom of the column (below the grid) upwards. When the boomerang hits any target, it will bounce off, make a $90$ degree turn to the right and fly off in a straight line in its new direction. The boomerang can hit multiple targets and does not stop until it leaves the grid.

  [Image] 

In the above example, $n=6$ and the black crosses are the targets. The boomerang in column $1$ (blue arrows) bounces $2$ times while the boomerang in column $3$ (red arrows) bounces $3$ times.

 The boomerang in column $i$ hits exactly $a_i$ targets before flying out of the grid. It is known that $a_i \leq 3$.

However, Zookeeper has lost the original positions of the targets. Thus, he asks you to construct a valid configuration of targets that matches the number of hits for each column, or tell him that no such configuration exists. If multiple valid configurations exist, you may print any of them.


-----Input-----

The first line contains a single integer $n$ $(1 \leq n \leq 10^5)$.

 The next line contains $n$ integers $a_1,a_2,\ldots,a_n$ $(0 \leq a_i \leq 3)$.


-----Output-----

If no configuration of targets exist, print $-1$.

 Otherwise, on the first line print a single integer $t$ $(0 \leq t \leq 2n)$: the number of targets in your configuration. 

 Then print $t$ lines with two spaced integers each per line. Each line should contain two integers $r$ and $c$ $(1 \leq r,c \leq n)$, where $r$ is the target's row and $c$ is the target's column. All targets should be different. 

 Every row and every column in your configuration should have at most two targets each. 


-----Examples-----
Input
6
2 0 3 0 1 1

Output
5
2 1
2 5
3 3
3 6
5 6

Input
1
0

Output
0

Input
6
3 2 2 2 1 1

Output
-1



-----Note-----

For the first test, the answer configuration is the same as in the picture from the statement.

 For the second test, the boomerang is not supposed to hit anything, so we can place $0$ targets.

 For the third test, the following configuration of targets matches the number of hits, but is not allowed as row $3$ has $4$ targets.

  [Image] 

It can be shown for this test case that no valid configuration of targets will result in the given number of target hits.

Difficulty: competition

Starter code:

Solutions:
import sys
readline = sys.stdin.readline

N = int(readline())
A = list(map(int, readline().split()))

Ans = []
one = []
tt = []
for i in range(N-1, -1, -1):
    a = A[i]
    if a == 0:
        continue
    if a == 1:
        Ans.append((i, i))
        one.append((i, i))
        continue
    if a == 2:
        if not one:
            Ans = None
            break
        else:
            oi, _ = one.pop()
            Ans.append((oi, i))
            tt.append((oi, i))
            continue
    else:
        if not tt:
            if not one:
                Ans = None
                break
            else:
                oi, wi = one.pop()
                Ans.append((i, wi))
                Ans.append((i, i))
                tt.append((i, i))
        else:
            oi, wi = tt.pop()
            Ans.append((i, wi))
            Ans.append((i, i))
            tt.append((i, i))
        continue

if Ans is None:
    print(-1)
else:
    print(len(Ans))
    if Ans:
        print('\n'.join(f'{a+1} {b+1}' for a, b in Ans))




n = int(input())
a = list(map(int, input().split()))

threes = []
twos = []
out = []
for i in range(n):
    if a[i] == 1:
        if twos:
            p = twos.pop()
            out.append((p, i))
        elif threes:
            p = threes.pop()
            out.append((p,i))
            out.append((i,i))
        else:
            out.append((i,i))
    elif a[i] == 2:
        if threes:
            p = threes.pop()
            out.append((p,i))
            out.append((i,i))
        else:
            out.append((i,i))

        twos.append(i)
    elif a[i] == 3:
        if threes:
            p = threes.pop()
            out.append((p,i))
            out.append((i,i))
        else:
            out.append((i,i))

        threes.append(i)
if twos or threes:
    print(-1)
else:
    print(len(out))
    print('\n'.join([str(x[0] + 1) + ' ' + str(x[1] + 1) for x in out]))


n = int(input())
lst = list(map(int,input().split()))
ans = []
nsp = 0
edpos = []
twpos = []
for i in range(n-1,-1,-1):
    if lst[i] == 1:
        ans.append([i, nsp])
        edpos.append([i, nsp])
        nsp += 1
    if lst[i] == 2:
        if len(edpos):
            k = edpos[-1]
            edpos.pop()
            ans.append([i, k[1]])
            twpos.append([i, k[1]])
        else:
            print(-1)
            return
    if lst[i] == 3:
        if len(twpos):
            k = twpos[-1]
            twpos.pop()
            ans.append([i, nsp])
            ans.append([k[0], nsp])
            twpos.append([i, nsp])
            nsp += 1
        elif len(edpos):
            k = edpos[-1]
            edpos.pop()
            ans.append([i, nsp])
            ans.append([k[0], nsp])
            twpos.append([i, nsp])
            nsp += 1
        else:
            print(-1)
            return
print(len(ans))
for i in ans:
    print(n - i[1], i[0] + 1)

import sys
input = sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
poss=True
col=[]
row=[]
cl=None
t=0
ts=[]
i=n-1
while i>=0:
    if a[i]==1:
        col.append(i)
        row.append(i)
        t+=1
        ts.append([i+1,i+1])
    if a[i]==2:
        if len(col)==0:
            poss=False
        else:
            t+=1
            r=row.pop()
            c=col.pop()
            ts.append([r+1,i+1])
            cl=i
    if a[i]==3:
        if cl!=None:
            t+=2
            ts.append([i+1,i+1])
            ts.append([i+1,cl+1])
            cl=i
        else:
            if len(col)==0:
                poss=False
            else:
                c=col.pop()
                r=row.pop()
                t+=2
                ts.append([i+1,i+1])
                ts.append([i+1,c+1])
                cl=i
    i-=1
if poss:
    print(t)
    for x in ts:
        print(*x)
else:
    print(-1)

n = int(input())
a = list(map(int, input().split()))
right_free = [] # dlya 2
right_busy = [] # dlya 3
ans = []
for i in range(n-1, -1, -1):
	if a[i] == 1:
		right_free.append(i)
	elif a[i] == 2:
		right_busy.append(i)
		if not right_free:
			print(-1)
			return
		x = right_free.pop()
		ans.append([i, i])
		ans.append([i, x])
	elif a[i] == 3:
		if not right_busy and not right_free:
			print(-1)
			return
		if right_busy:
			x = right_busy.pop()
			ans.append([i, i])
			ans.append([i, x])
		else:
			x = right_free.pop()
			ans.append([i, i])
			ans.append([x, x])
			ans.append([i, x])
		right_busy.append(i)
while right_free:
	x = right_free.pop()
	ans.append([x, x])
print(len(ans))
for x,y in ans:
	print(x+1, y+1)



n = int(input())
a = list(map(int, input().split()))
if a[-1] > 1:
    print(-1)
    return
s = set()
s2 = []
s3 = []
r = 1
for i in range(n):
    if a[i] == 1:
        if s2:
            x = s2.pop()
            s.add((x, i + 1))
        elif s3:
            x = s3.pop()
            s.add((x, i + 1))
            s.add((r, i + 1))
            r += 1
        else:
            s.add((r, i + 1))
            r += 1
    elif a[i] == 2:
        if s3:
            x = s3.pop()
            s.add((x, i + 1))
            s.add((r, i + 1))
            s2.append(r)
            r += 1
        else:
            s.add((r, i + 1))
            s2.append(r)
            r += 1
    elif a[i] == 3:
        if s3:
            x = s3.pop()
            s.add((x, i + 1))
            s.add((r, i + 1))
            s3.append(r)
        else:
            s.add((r, i + 1))
            s3.append(r)
        r += 1
    else:
        r += 1
if s2 or s3:
    print(-1)
else:
    print(len(s))
    for x in s:
        print(x[0], x[1])


n = int(input())
aa = list(map(int, input().split()))
r = 1
pen2 = []
pen3 = []
ans = []
for c, a in enumerate(aa, 1):
    if a == 0:
        pass
    elif a == 1:
        if pen2:
            b = pen2.pop()
            ans.append((b, c))
        elif pen3:
            b = pen3.pop()
            ans.append((b, c))
            ans.append((r, c))
            r += 1
        else:
            ans.append((r, c))
            r += 1
    elif a == 2:
        pen2.append(r)
        if pen3:
            b = pen3.pop()
            ans.append((b, c))
            ans.append((r, c))
            r += 1
        else:
            ans.append((r, c))
            r += 1
    else:
        if pen3:
            b = pen3.pop()
            ans.append((b, c))
            ans.append((r, c))
            pen3.append(r)
            r += 1
        else:
            ans.append((r, c))
            pen3.append(r)
            r += 1

if r > (n + 1) or pen2 or pen3:
    print(-1)
else:
    print(len(ans))
    print('\n'.join(' '.join(map(str, x)) for x in ans))


n = int(input())

a = [0] + list(map(int, input().split()))

b = []
poss = True

ones = []
twos = []
threes = []

row_num = n


for c in range(n, 0, -1):
    if a[c] == 0:
        continue

    elif a[c] == 1:
        ones.append((row_num, c))
        b.append((row_num, c))
        row_num -= 1

    elif a[c] == 2:
        if len(ones) > 0:
            q = ones.pop()
            b.append((q[0], c))

            twos.append((q[0], c))
            
        else:
            poss = False

    elif a[c] == 3:
        if len(threes) > 0:
            q = threes.pop()

            b.append((row_num, c))
            b.append((row_num, q[1]))
            threes.append((row_num, c))
            
            row_num -= 1
            
        elif len(twos) > 0:
            q = twos.pop()

            b.append((row_num, c))
            b.append((row_num, q[1]))
            threes.append((row_num, c))
            
            row_num -= 1


        elif len(ones) > 0:
            q = ones.pop()

            b.append((row_num, c))
            b.append((row_num, q[1]))
            threes.append((row_num, c))
            
            row_num -= 1

        else:
            poss = False

if poss:
    print(len(b))
    for item in b:
        print(item[0], item[1])
else:
    print(-1)
    


import sys
n=int(input())
a=list(map(int,input().split()))
height=n
ans=[]
last3=-1
fail=0
used=-1
for i in range(n):
    if a[i]==3:
        if height==n:
            ans.append((n-height+1,i+1))
            height-=1
        else:
            ans.append((n+1-(height+1),i+1))
            ans.append((n+1-height,i+1))
            height-=1
        last3=i
if last3==n-1:
    print(-1)
    return
if last3>-1:
    flag=0
    for i in range(last3,n):
        if a[i]==2:
            flag=1
            ans.append((n+1-(height+1),i+1))
            height-=1
            break
    if flag==0:
        flag2=0
        for i in range(last3,n):
            if a[i]==1:
                ans.append((n+1-(height+1),i+1))
                height-=1
                flag2=1
                used=i
                break
        if flag2==0:
            print(-1)
            return
ones=[]
if used==-1:
    height-=1
for i in range(n-1,-1,-1):
    if a[i]==1 and i!=used:
        ones.append(i)
    if a[i]==2:
        if len(ones)==0:
            print(-1)
            return
        k=ones.pop()
        ans.append((n+1-(height+1),i+1))
        ans.append((n+1-(height+1),k+1))
        height-=1
if used>-1:
    ones.append(used)
for i in ones:
    ans.append((n+1-(height+1),i+1))
    height-=1
print(len(ans))
for x,y in ans:
    print(x,y)

def main():
    import sys
    input = sys.stdin.readline
    
    n = int(input())
    ans = []
    arr = list(map(int, input().split()))
    amt = [2 if x else 0 for x in arr]
    
    bottoms = []
    bottoms1 = []
    others = []
    idx = 0
    idx1 = 0
    
    for i in range(n-1, -1, -1):
        if arr[i] == 0:
            continue
        if arr[i] == 1:
            bottoms.append((i + 1, i + 1))
        if arr[i] == 2:
            if idx == len(bottoms):
                print(-1)
                return
            
            r, c = bottoms[idx]
            bottoms1.append((r, i + 1))
            idx += 1
        if arr[i] == 3:
            if idx == len(bottoms) and idx1 == len(bottoms1):
                print(-1)
                return
            elif idx1 == len(bottoms1):
                r, c = bottoms[idx]
                bottoms1.append((i + 1, i + 1))
                others.append((i + 1, c))
                idx += 1
            else:
                r, c = bottoms1[idx1]
                bottoms1.append((i + 1, i + 1))
                others.append((i + 1, c))
                idx1 += 1
    
    # if arr[-1] > 1:
    #     print(-1)
    #     return
    # elif arr[-1] == 1:
    #     amt[-1] -= 1
    #     ans.append((n, n))
    # x = -1
    # y = -1
    # rindex = n - 1
    # for i in range(n - 1, -1, -1):
    #     if arr[i] == 0:
    #         continue
    #     elif arr[i] == 1:
    #         amt[i] -= 1
    #         ans.append((i + 1, i + 1))
            
    #         if y == -1:
    #             x = i
    #             y = i + 1
    #     elif arr[i] == 2:
    #         if y == -1:
    #             print(-1)
    #             return
            
    #         amt[i] -= 1
    #         ans.append((y, i + 1))
    #     elif arr[i] == 3:
    #         if x == -1:
    #             print(-1)
    #             return
    #         while rindex > i and (rindex == x or not arr[rindex]):
    #             rindex -= 1
    #         if rindex == i:
    #             print(-1)
    #             return
    #         amt[i] -= 1
    #         amt[rindex] -= 1
    #         ans.append((i + 1, i + 1))
    #         ans.append((i + 1, rindex + 1))
    
    ans = others + bottoms + bottoms1
    print(len(ans))
    for (x, y) in ans:
        print(x, y)
    return 0

main()


from sys import stdin
import sys

n = int(stdin.readline())
a = list(map(int,stdin.readline().split()))

one = []
ttt = []
ans = []

for i in range(n,0,-1):

    now = a[i-1]
    if now == 0:
        continue
    elif now == 1:
        ans.append((i,i))
        one.append(i)
    elif now == 2:
        if len(one) == 0:
            print (-1)
            return
        ans.append((one[-1],i))
        del one[-1]
        ttt.append(i)
    elif now == 3:
        if len(ttt) == 0:
            if len(one) == 0:
                print (-1)
                return
            ans.append((i,i))
            ans.append((i,one[-1]))
            del one[-1]
            ttt.append(i)
        else:
            ans.append((i,i))
            ans.append((i,ttt[-1]))
            del ttt[-1]
            ttt.append(i)

print (len(ans))
for i in ans:
    print (*i)

N, = list(map(int, input().split()))
X = list(map(int, input().split()))
from collections import deque
R = []
A1 = []
A2 = []
ng = 0
for i in range(N-1, -1, -1):
    j = N-1-i+1
    if X[i] == 1:
        R.append((i+1, j))
        A1.append((i+1, j))
    elif X[i] == 2:
        if not A1:
            ng = 1
            break
        x, y = A1.pop()
#        R.append((i+1, y))
        R.append((i+1, y))
        A2.append((i+1, y))
    elif X[i] == 3:
        if A2:
            x, y = A2.pop()
            R.append((x, j))
            R.append((i+1, j))
            A2.append((i+1, j))
        elif A1:
            x, y = A1.pop()
            R.append((x, j))
            R.append((i+1, j))
            A2.append((i+1, j))
        else:
            ng = 1
if ng:
    print(-1)
else:
    print(len(R))
    for x, y in R:
#        print(x, y)
        print(N-y+1, x)


n = int(input())
a = list(map(int, input().split()))
ans = []

three = []
two = []
for i in range(n):
    if a[i] == 0:
        continue
    if a[i] == 3:
        if len(three) > 0:
            x = three.pop()
            ans.append((x, i))
            ans.append((i, i))
            three.append(i)
        else:
            ans.append((i, i))
            three.append(i)
            
    elif a[i] == 2:
        if len(three) > 0:
            x = three.pop()
            ans.append((x, i))
            ans.append((i, i))
            two.append(i)
        else:
            ans.append((i, i))
            two.append(i)

    else:
        if len(three) > 0:
            x = three.pop()
            ans.append((x, i))
            ans.append((i, i))
        elif len(two) > 0:
            x = two.pop()
            ans.append((x, i))
        else:
            ans.append((i, i))

if len(three) > 0 or len(two) > 0:
    print(-1)

else:
    print(len(ans))
    for i, j in ans:
        print(i+1, j+1)



n = int(input())

x = []
y = []

ans = []

A = list(map(int, input().split()))

for i in range(n):
    
    if A[i] == 1:
        
        if y:
            
            ans += [[y.pop(), i + 1]]
        
        elif x:
            
            ans += [[x.pop(), i + 1]]
            ans += [[i + 1, i + 1]]
            
        else:
            
            ans += [[i + 1, i + 1]]
            
    elif A[i] == 2:
        
        
        
        if x:
            ans += [[x.pop(), i + 1]]
            ans += [[i + 1, i + 1]]
            
            
            
        else:
            ans += [[i + 1, i + 1]]
            
        
        y += [i + 1]
            
    elif A[i] == 3:
        
        
        if x:
            
            ans += [[x.pop(), i + 1]]
            ans += [[i + 1, i + 1]]
            
            
        else:
            ans += [[i + 1, i + 1]]
        
        x += [i + 1]
        
            
if x or y:
    
    print(-1)
    
else:
    
    print(len(ans))
    
    for Ans in ans:
        
        print(*Ans)

n = int(input())
a = list(map(int, input().split()))

twos = []
threes = []
pts = []
for i,q in enumerate(a):
	i = i + 1
	if q == 0:
		# no targets
		pass
	elif q == 1:
		if twos:
			pts += [(twos.pop(), i)]
		elif threes:
			pts += [(threes.pop(), i), (i, i)]
		else:
			pts += [(i,i)]
	elif q == 2:
		pts += [(i,i)]
		if threes:
			pts += [(threes.pop(), i)]
		twos += [i]
	elif q == 3:
		pts += [(i,i)]
		if threes:
			pts += [(threes.pop(), i)]
		threes += [i]

if not twos and not threes:
	print(len(pts))
	for x in pts:
		print(*x)
else:
	print(-1)


n = int(input())
A = list(map(int, input().split()))
max_not_used = n
ones = []
twos = []
targets = []
failed = False
for c, a in zip(list(range(n, 0, -1)), reversed(A)):
    if a == 1:
        r = max_not_used
        max_not_used -= 1
        targets.append((r, c))
        ones.append((r, c))
    elif a == 2:
        if not ones:
            failed = True
            break
        else:
            r, __ = ones.pop()
            targets.append((r, c))
            twos.append((r, c))
    elif a == 3:
        if (not ones) and (not twos):
            failed = True
            break
        else:
            if twos:
                rr, cc = twos.pop()
            else:
                rr, cc = ones.pop()
            r = max_not_used
            max_not_used -= 1
            targets.append((r, c))
            targets.append((r, cc))
            twos.append((r, c))
if failed:
    print(-1)
else:
    print(len(targets))
    for target in targets:
        print(*target)