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.InputStreamReader;
import java.io.IOException;
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);
		for (int i = r; 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) {
					xor(x, i, j, true);
				}
			}
		}
		boolean[][] needs = new boolean[r][r];
		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]) {
				// This vector is not in the basis for y but
				// we still may need it as a part of the basis for x,
				// so keep it for now
				later.add(step);
			} else {
				for (int i = 0; i < r; i++) {
					if (i != step && needs[step][i]) {
						xor(x, step, i, 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);
				}
			}
		}
		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 r = 0;
		for (int j = 0; j < 32; j++) {
			int i;
			for (i = r; i < n; i++) {
				if ((x[i] & (1 << j)) != 0) {
					break;
				}
			}
			if (i == n) {
				continue;
			}
			swap(x, i, r, addToAns);
			for (i = r + 1; i < n; i++) {
				if ((x[i] & (1 << j)) != 0) {
					xor(x, i, r, addToAns);
				}
			}
			++r;
		}
		return r;
	}

	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());
	}

}