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;
#pragma comment(linker, "/STACK:255000000")
bool firstout = 1;
template <class T>
T &minn(T &a, T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
T &maxx(T &a, T b) {
  if (a < b) a = b;
  return a;
}
int &madd(int &a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
int &msub(int &a, int b) {
  a -= b;
  if (a < 0) a += 1000000007;
  return a;
}
int &mmult(int &a, int b) { return a = (long long)a * b % 1000000007; }
int mdiv(long long a, long long b, long long m) {
  a = (a % m + m) % m;
  b = (b % m + m) % m;
  if (a % b == 0) return a / b;
  return (a + m * mdiv(-a, m, b)) / b;
}
int n, m, q;
int X[10123];
int Y[10123];
int A[30][10123];
int P[30];
int mask;
vector<pair<int, int> > ans;
int oddb(int a) {
  int r = 0;
  for (; a; a &= a - 1) r ^= 1;
  return r;
}
void mkswap(int i, int j) {
  if (i != j) {
    ans.push_back(make_pair(i, j));
    ans.push_back(make_pair(j, i));
    ans.push_back(make_pair(i, j));
  }
}
void con() {
  if (mask == (1 << m) - 1) return;
  int i, j, k;
  for (i = (0); i < (m); ++i)
    if (!((mask >> i) & 1) && Y[P[i]]) break;
  if (i == m) {
    for (i = (0); i < (m); ++i)
      if (!((mask >> i) & 1)) ans.push_back(make_pair(P[i], P[i]));
    return;
  }
  int a = Y[P[i]];
  for (j = (0); j < (m); ++j)
    if ((a >> j) & 1) {
      mkswap(P[i], P[j]);
      swap(P[i], P[j]);
      i = j;
      break;
    }
  for (j = (0); j < (m); ++j)
    if (i != j && ((a >> j) & 1)) {
      ans.push_back(make_pair(P[i], P[j]));
    }
  vector<int> v;
  v.clear();
  for (j = (0); j < (m); ++j)
    if ((Y[P[j]] >> i) & 1) {
      Y[P[j]] ^= a;
      if (j != i) v.push_back(P[j]);
    }
  mask |= (1 << i);
  i = P[i];
  con();
  for (k = (0); k < (v.size()); ++k) {
    j = v[k];
    ans.push_back(make_pair(j, i));
  }
}
int main() {
  int i, j, k;
  char c;
  int a, d;
  int ts;
  for (ts = 1; scanf("%"
                     "d",
                     &(n)) > 0;
       ++ts) {
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(X[i]));
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(Y[i]));
    for (i = (0); i < (30); ++i) {
      for (j = (0); j < (n); ++j) A[i][j] = (X[j] >> i) & 1;
      A[i][j] = 1 << i;
    }
    m = 0;
    for (i = (0); i < (30); ++i) {
      int a = n;
      int ii = 1012345678;
      for (k = (i); k < (30); ++k) {
        for (j = (0); j < (n); ++j)
          if (A[k][j]) break;
        if (j < a) a = j, ii = k;
      }
      if (a == n) break;
      P[m++] = a;
      for (j = (0); j < (n + 1); ++j) swap(A[i][j], A[ii][j]);
      for (k = (i + 1); k < (30); ++k)
        if (A[k][a])
          for (j = (0); j < (n + 1); ++j) A[k][j] ^= A[i][j];
    }
    for (k = (0); k < (n); ++k) {
      int res = 0;
      int a = Y[k];
      for (i = (30) - 1; i >= (m); --i) {
        if (oddb(a & A[i][n])) break;
      }
      if (i >= m) break;
      for (i = (m)-1; i >= (0); --i) {
        int r = oddb(a & A[i][n]);
        for (j = (i + 1); j < (m); ++j)
          if (A[i][P[j]] && ((res >> j) & 1)) r ^= 1;
        res |= r << i;
      }
      Y[k] = res;
    }
    if (k < n)
      printf(
          "%"
          "d",
          (-1)),
          printf("\n"), firstout = 1;
    else {
      ans.clear();
      for (i = (0); i < (n); ++i) {
        for (j = (0); j < (m); ++j)
          if (P[j] == i) break;
        if (j == m) {
          ans.push_back(make_pair(i, i));
          for (j = (0); j < (m); ++j)
            if ((Y[i] >> j) & 1) ans.push_back(make_pair(i, P[j]));
        }
      }
      mask = 0;
      con();
      printf(
          "%"
          "d",
          (ans.size()));
      printf("\n"), firstout = 1;
      for (i = (0); i < (ans.size()); ++i)
        printf((firstout) ? "%"
                            "d"
                          : " %"
                            "d",
               (ans[i].first + 1)),
            firstout = 0,
            printf((firstout) ? "%"
                                "d"
                              : " %"
                                "d",
                   (ans[i].second + 1)),
            firstout = 0, printf("\n"), firstout = 1;
    }
  }
  return 0;
}