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;
const int N = (int)1e4 + 11;
const int M = 33;
using pii = pair<int, int>;
using vpii = vector<pii>;
int x[N], y[N];
int lb(int x) { return x & (-x); }
int y_comb[M];
vpii gauss(int x[], int n, int &b) {
  vpii ret;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < b; j++)
      if (lb(x[j]) & x[i]) {
        x[i] ^= x[j];
        ret.push_back({i, j});
      }
    if (x[i]) {
      for (int j = 0; j < b; j++)
        if (lb(x[i]) & x[j]) {
          x[j] ^= x[i];
          ret.push_back({j, i});
        }
      if (i != b) {
        swap(x[i], x[b]);
        ret.push_back({i, b});
        ret.push_back({b, i});
        ret.push_back({i, b});
      }
      b++;
    }
  }
  return ret;
}
int p[M];
int cx[N];
int main() {
  ios ::sync_with_stdio(false);
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> x[i];
    cx[i] = x[i];
  }
  for (int i = 0; i < n; i++) cin >> y[i];
  int xb = 0, yb = 0;
  vpii p1 = gauss(x, n, xb);
  vpii p3 = gauss(y, n, yb);
  bool f = true;
  for (int i = 0; i < yb; i++) {
    for (int j = 0; j < xb; j++)
      if (lb(x[j]) & y[i]) {
        y[i] ^= x[j];
        y_comb[i] |= (1 << j);
      }
    if (y[i]) f = false;
  }
  if (!f) {
    cout << "-1\n";
    return 0;
  }
  for (int i = 0; i < yb; i++) {
    for (int j = 0; j < i; j++)
      if (lb(y_comb[j]) & y_comb[i]) {
        y_comb[i] ^= y_comb[j];
        p3.push_back({i, j});
      }
    for (int j = 0; j < i; j++)
      if (lb(y_comb[i]) & y_comb[j]) {
        y_comb[j] ^= y_comb[i];
        p3.push_back({j, i});
      }
  }
  reverse(p3.begin(), p3.end());
  vpii p2;
  iota(p, p + xb, 0);
  for (int i = 0; i < yb; i++) {
    int now = y_comb[i];
    for (int j = 0; j < i; j++)
      if ((now >> p[j]) & 1) {
        now ^= y_comb[j];
        p2.push_back({i, j});
      }
    int l = __builtin_ctz(now);
    if (p[i] != l) {
      int t = -1;
      for (int j = i + 1; j < xb; j++)
        if (p[j] == l) t = j;
      swap(p[i], p[t]);
      p2.push_back({i, t});
      p2.push_back({t, i});
      p2.push_back({i, t});
    }
    for (int j = i + 1; j < xb; j++)
      if ((now >> p[j]) & 1) {
        p2.push_back({i, j});
        now ^= (1 << p[j]);
      }
  }
  for (int i = yb; i < xb; i++) p2.push_back({i, i});
  cout << p1.size() + p2.size() + p3.size() << '\n';
  for (vpii v : {p1, p2, p3}) {
    for (pii p : v) cout << p.first + 1 << ' ' << p.second + 1 << '\n';
  }
  return 0;
}