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:
import java.util.List;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskF solver = new TaskF();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskF {
	public void solve(int testNumber, FastScanner in, PrintWriter out) {
		int n = in.nextInt();
		int[] x = new int[n];
		int[] y = new int[n];
		for (int i = 0; i < n; i++) {
			x[i] = in.nextInt();
		}
		for (int i = 0; i < n; i++) {
			y[i] = in.nextInt();
		}
		int r = rank(x, true);
		int[] both = new int[2*n];
		System.arraycopy(x, 0, both, 0, n);
		System.arraycopy(y, 0, both, n, n);
		int rBoth = rank(both, false);
		if (r != rBoth) {
			out.println(-1);
			return;
		}
		int[] basis = new int[r];
		System.arraycopy(x, 0, basis, 0, r);
		boolean[][] needs = new boolean[r][r];
		for (int i = 0; i < n; i++) {
			int vec = y[i];
			for (int j = 0; j < r; j++) {
				int[] tmp = basis.clone();
				tmp[j] = vec;
				if (rank(tmp, false) == r) {
					if (i < r) {
						needs[i][j] = true;
					} else {
						xor(x, i, j, true);
					}
				}
			}
		}
		for (int i = r; i < n; i++) {
			if (x[i] != y[i]) {
				throw new AssertionError("a non-match outside of the basis: " + r + " " + i + " " + x[i] + " " + y[i]);
			}
		}
		List<Integer> later = new ArrayList<Integer>();
		for (int step = 0; step < r; step++) {
			System.arraycopy(x, 0, basis, 0, r);
			needs = new boolean[r][r];
			for (int i = 0; i < r; i++) {
				int vec = y[i];
				for (int j = 0; j < r; j++) {
					int[] tmp = basis.clone();
					tmp[j] = vec;
					if (rank(tmp, false) == r) {
						needs[i][j] = true;
					}
				}
			}
			if (!needs[step][step]) {
				for (int i = step + 1; i < r; i++) {
					if (needs[step][i]) {
						swap(x, step, i, true);
						break;
					}
				}
			}
			System.arraycopy(x, 0, basis, 0, r);
			needs = new boolean[r][r];
			for (int i = 0; i < r; i++) {
				int vec = y[i];
				for (int j = 0; j < r; j++) {
					int[] tmp = basis.clone();
					tmp[j] = vec;
					if (rank(tmp, false) == r) {
						needs[i][j] = true;
					}
				}
			}
			if (!needs[step][step]) {
				later.add(step);
			} else {
				for (int q = 0; q < r; q++) {
					if (q != step && needs[step][q]) {
						xor(x, step, q, true);
					}
				}
			}
		}
		for (int it = later.size() - 1; it >= 0; it--) {
			int i = later.get(it);
			xor(x, i, i, true);
			for (int j = 0; j < i; j++) {
				if (needs[i][j]) {
					xor(x, i, j, true);
				}
			}
		}
		for (int i = 0; i < r; i++) {
			if (x[i] != y[i]) {
				throw new AssertionError(r + " " + i + " " + x[i] + " " + y[i]);
			}
		}
		out.println(ans.size());
		for (String s : ans) {
			out.println(s);
		}
	}

	List<String> ans = new ArrayList<String>();

	private int rank(int[] x, boolean addToAns) {
		int n = x.length;
		int res = 0;
		int bits = 0; // important ones: we do not want to rearrange columns
		int numZero = 0;
		for (int r = 0; r < n - numZero; r++) {
			int i;
			int j = -1;
			outer:
			for (i = r; i < n - numZero; i++) {
				for (j = 0; j < 32; j++) {
					if ((bits & (1 << j)) == 0 && (x[i] & (1 << j)) != 0) {
						break outer;
					}
				}
			}
			if (i == n - numZero) {
				return res;
			}
			++res;
			bits |= 1 << j;
			swap(x, i, r, addToAns);
			for (i = r + 1; i < n - numZero; i++) {
				if ((x[i] & (1 << j)) != 0) {
					xor(x, i, r, addToAns);
				}
				if (x[i] == 0) {
					swap(x, i, n - numZero - 1, addToAns);
					--i;
					++numZero;
				}
			}
		}
		return res;
	}

	private void xor(int[] x, int i, int j, boolean addToAns) {
		x[i] ^= x[j];
		if (addToAns) {
			ans.add((i + 1) + " " + (j + 1));
		}
	}

	private void swap(int[] x, int i, int j, boolean addToAns) {
		if (i == j) {
			return;
		}
		int t = x[i];
		x[i] = x[j];
		x[j] = t;
		if (addToAns) {
			ans.add((i + 1) + " " + (j + 1));
			ans.add((j + 1) + " " + (i + 1));
			ans.add((i + 1) + " " + (j + 1));
		}
	}
}

class FastScanner {

	private BufferedReader in;
	private StringTokenizer st;

	public FastScanner(InputStream stream) {
		in = new BufferedReader(new InputStreamReader(stream));
	}

	public String next() {
		while (st == null || !st.hasMoreTokens()) {
			try {
				String rl = in.readLine();
				if (rl == null) {
					return null;
				}
				st = new StringTokenizer(rl);
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return st.nextToken();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

}