Problem: There are some tasks which have the following structure: you are given a model, and you can do some operations, you should use these operations to achive the goal. One way to create a new task is to use the same model and same operations, but change the goal.

Let's have a try. I have created the following task for Topcoder SRM 557 Div1-Hard: you are given n integers x1, x2, ..., xn. You are allowed to perform the assignments (as many as you want) of the following form xi ^= xj (in the original task i and j must be different, but in this task we allow i to equal j). The goal is to maximize the sum of all xi.

Now we just change the goal. You are also given n integers y1, y2, ..., yn. You should make x1, x2, ..., xn exactly equal to y1, y2, ..., yn. In other words, for each i number xi should be equal to yi.

Input

The first line contains an integer n (1 ≤ n ≤ 10000). The second line contains n integers: x1 to xn (0 ≤ xi ≤ 109). The third line contains n integers: y1 to yn (0 ≤ yi ≤ 109).

Output

If there is no solution, output -1.

If there is a solution, then in the first line output an integer m (0 ≤ m ≤ 1000000) – the number of assignments you need to perform. Then print m lines, each line should contain two integers i and j (1 ≤ i, j ≤ n), which denote assignment xi ^= xj.

If there are multiple solutions you can print any of them. We can prove that under these constraints if there exists a solution then there always exists a solution with no more than 106 operations.

Examples

Input

2
3 5
6 0


Output

2
1 2
2 2


Input

5
0 0 0 0 0
1 2 3 4 5


Output

-1


Input

3
4 5 6
1 2 3


Output

5
3 1
1 2
2 2
2 3
3 1


Input

3
1 2 3
4 5 6


Output

-1

Note

Assignment a ^= b denotes assignment a = a ^ b, where operation "^" is bitwise XOR of two integers.

Solution (in JAVA):

Solution:
var xAction = new Array();
var yAction = new Array();
var xBit = 0;
var yBit = 0;

var n = parseInt(readline());
var x = readline().split(' ');
for(var i=0;i<n;i++)
{
    x[i] = parseInt(x[i]);
}
var y = readline().split(' ');
for(var i=0;i<n;i++)
{
    y[i] = parseInt(y[i]);
}

var res = new Array();
var ans = 1;

parseArray(x,xAction,'x');
parseArray(y,yAction,'y');

if(xBit<yBit)
{
    ans = 0;
}
else
{
    ans = updateBaseBit();
//	debugA();
	if(ans==1)
	{
	    for(var i=xBit;i<n;i++)
		{
		    ans = updateNum(i,0,xBit,y[i])
			if(ans==0)
			{
			    break;
			}
		}
	}
}

if(ans==0)
{
    print(-1);
}
else
{
    var step = (xAction.length + yAction.length)/2;
	print(step);
	for(var i=0;i<xAction.length;i+=2)
	{
	    xAction[i]++;
		xAction[i+1]++;
	    print(xAction[i]+' '+xAction[i+1]);
	}
	for(var i=yAction.length-1;i>0;i-=2)
	{
	    yAction[i]++;
		yAction[i-1]++;
	    print(yAction[i-1]+' '+yAction[i]);
	}
}



// functions

// move highest bit to the head of the array
function parseArray(aNumber, aAction, strType)
{
    var nBit = 0;
	for(var k=30; k>=0; k--)
	{
    	for(var i=nBit;i<aNumber.length;i++)
	    {
	        if(isKBit(aNumber[i],k))
			{
			    for(var j=i+1;j<aNumber.length;j++)
				{
				    if(isKBit(aNumber[j],k))
					{
					    xor(j,i,aNumber,aAction);
					}
				}
			    swap(nBit,i,aNumber,aAction);
				nBit++;
			    break;
			}
	    }
	}
	if(strType=='x')
	{
	    xBit = nBit;
	}
	else
	{
	    yBit = nBit;
	}
}

// make the base bit of x and y equivalent
function updateBaseBit()
{
    var pos = 0;
    while(pos<=xBit||pos<=yBit)
	{
	    if(pos==yBit)
		{
		    xBit = yBit;
		    return 1;
		}
		if(pos==xBit)
		{
		    return 0;
		}
		
		var t = getHighestBit(x[pos])-getHighestBit([y[pos]]);
		if(t<0)
		{
		    return 0;
		}
		if(t>0)
		{
		    xor(pos,pos,x,xAction);
		}
		var tt=updateNum(pos,pos+1,xBit,y[pos]);

		if(tt==0)
		{
		    return 0;
		}
		pos++;
	}
}

// convert x[k] into val with x[s, s+1,...,e-1]
function updateNum(k,s,e,val)
{
    if(val==0)
	{
	    xor(k,k,x,xAction);
		return 1;
	}
	for(var i=s;i<e;i++)
	{
	    var t = getHighestBit(x[k]^val)-getHighestBit(x[i]);
	    if(t==0)
		{
		    xor(k,i,x,xAction);
		}
		else if(t>0)
		{
		    return 0;
		}
	}
	if(x[k]==val)
	{
	    return 1;
	}
	else
	{
	    return 0;
	}
}

function swap(i,j,aNumber,aAction)
{
    if(i != j)
	{
        var t = aNumber[i];
	    aNumber[i] = aNumber[j];
	    aNumber[j] = t;
	    aAction.push(i,j,j,i,i,j);
	}
}

function isKBit(x, k)
{
    if(((x>>k)&1)!=0)
	{
	    return 1;
	}
	else
	{
	    return 0;
	}
}

function getHighestBit(val)
{
    var x =0;
	while(val>0)
	{
	    val =(val>>1);
		x++;
	}
	return x-1;
}

function xor(i,j,aNumber,aAction)
{
    aNumber[i]^=aNumber[j];
	aAction.push(i,j);
}

function debugA()
{
	print('ans: '+ans);
	for(var i=0;i<n;i++)
	{
		print('x['+i+']: '+x[i]);
	}
	for(var i=0;i<n;i++)
	{
		print('y['+i+']: '+y[i]);
	}
	print('xBit: '+xBit+'  yBit: '+yBit);
	print('xAction length: '+ xAction.length);
	print('yAction length: '+yAction.length);
}