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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1000010], b[1000010], Aa[1000010], Ab[1000010], Ba[1000010], Bb[1000010];
void Swap(int *A, int *ansA, int *ansB, int x, int y, int &step) {
  A[x] ^= A[y];
  A[y] ^= A[x];
  A[x] ^= A[y];
  ansA[step] = x;
  ansB[step] = y;
  step++;
  ansA[step] = y;
  ansB[step] = x;
  step++;
  ansA[step] = x;
  ansB[step] = y;
  step++;
}
void Sort(int *A, int *ansA, int *ansB, int &step) {
  int i, j, k, l = 1;
  for (i = 30; i >= 0; i--) {
    for (j = l; j <= n; j++) {
      if ((A[j] >> i) & 1) {
        if (j != l) Swap(A, ansA, ansB, l, j, step);
        for (k = 1; k <= n; k++) {
          if (((A[k] >> i) & 1) && (k != l)) {
            A[k] ^= A[l];
            ansA[step] = k;
            ansB[step] = l;
            step++;
          }
        }
        l++;
        break;
      }
    }
  }
  return;
}
int main() {
  bool flag;
  int i, j, k, stepA, stepB;
  while (~scanf("%d", &n)) {
    for (i = 1; i <= n; i++) scanf("%d", a + i);
    for (i = 1; i <= n; i++) scanf("%d", b + i);
    stepA = stepB = 0;
    Sort(a, Aa, Ab, stepA);
    Sort(b, Ba, Bb, stepB);
    for (i = 1; i <= n; i++) {
      if (!a[i]) break;
      k = 30;
      while (((a[i] >> k) & 1) == 0) k--;
      for (j = 1; j <= 31 && j <= n; j++)
        if (((a[j] ^ b[j]) >> k) & 1) {
          a[j] ^= a[i];
          Aa[stepA] = j;
          Ab[stepA] = i;
          stepA++;
        }
    }
    flag = true;
    for (i = 1; i <= n; i++)
      if (a[i] != b[i]) {
        flag = false;
        break;
      }
    if (!flag) {
      puts("-1");
      continue;
    }
    printf("%d\n", stepA + stepB);
    for (i = 0; i < stepA; i++) printf("%d %d\n", Aa[i], Ab[i]);
    for (i = stepB - 1; i >= 0; i--) printf("%d %d\n", Ba[i], Bb[i]);
  }
  return 0;
}