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 bits = 40;
bool success;
vector<int> toVector(int x) {
  vector<int> transformed;
  for (int i = 0; i < bits; ++i) {
    transformed.push_back(x % 2);
    x /= 2;
  }
  return transformed;
}
void addTo(vector<int> &v1, vector<int> &v2) {
  for (int i = 0; i < v1.size(); ++i) v1[i] = (v1[i] + v2[i]) % 2;
}
vector<int> gauss(vector<vector<int> > &matrix, vector<int> column) {
  success = true;
  int m = matrix.size();
  vector<int> units(m, 0);
  vector<vector<int> > reverseMatrix;
  reverseMatrix.assign(bits, vector<int>(m));
  for (int i = 0; i < bits; ++i)
    for (int j = 0; j < m; ++j) reverseMatrix[i][j] = matrix[j][i];
  int high = -1;
  for (int j = 0; j < m; ++j) {
    int i;
    for (i = high + 1; i < bits; ++i)
      if (reverseMatrix[i][j] != 0) break;
    if (i == bits) continue;
    ++high;
    swap(reverseMatrix[high], reverseMatrix[i]);
    swap(column[i], column[high]);
    for (int ii = 0; ii < bits; ++ii) {
      if (ii == high) continue;
      if (reverseMatrix[ii][j] == 0) continue;
      addTo(reverseMatrix[ii], reverseMatrix[high]);
      column[ii] = (column[ii] + column[high]) % 2;
    }
  }
  for (int i = 0; i < 40; ++i) {
    if (column[i] == 0) continue;
    int j;
    for (j = 0; j < m; ++j)
      if (reverseMatrix[i][j] == 1) break;
    if (j < m)
      units[j] = 1;
    else
      success = false;
  }
  return units;
}
vector<int> gauss(vector<int> &basis, int column) {
  vector<vector<int> > matrix;
  for (size_t i = 0; i < basis.size(); ++i)
    matrix.push_back(toVector(basis[i]));
  vector<int> newColumn = toVector(column);
  return gauss(matrix, newColumn);
}
int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> x(n);
  vector<int> y(n);
  for (int i = 0; i < n; ++i) cin >> x[i];
  for (int i = 0; i < n; ++i) cin >> y[i];
  vector<int> xx = x;
  vector<int> yy = y;
  int col = 0;
  while (col < n && x[col] == 0) ++col;
  if (col == n) {
    int ycol = 0;
    while (ycol < n && y[ycol] == 0) ++ycol;
    if (ycol == n) {
      cout << 0;
      return 0;
    } else {
      cout << -1;
      return 0;
    }
  }
  vector<int> numbers;
  vector<int> basis;
  numbers.push_back(col);
  basis.push_back(x[col]);
  for (int i = col + 1; i < n; ++i) {
    gauss(basis, x[i]);
    if (!success) {
      numbers.push_back(i);
      basis.push_back(x[i]);
    }
  }
  vector<pair<int, int> > answer;
  set<int> basnums;
  for (int i = 0; i < numbers.size(); ++i) {
    basnums.insert(numbers[i]);
  }
  vector<vector<int> > basvectors;
  for (int i = 0; i < numbers.size(); ++i)
    basvectors.push_back(toVector(x[numbers[i]]));
  for (int i = 0; i < n; ++i) {
    if (basnums.count(i)) continue;
    answer.push_back(make_pair(i, i));
    vector<int> ycolumn = toVector(y[i]);
    vector<int> units = gauss(basvectors, ycolumn);
    if (!success) {
      cout << -1;
      return 0;
    }
    for (int j = 0; j < units.size(); ++j)
      if (units[j]) answer.push_back(make_pair(i, numbers[j]));
  }
  vector<bool> finals(numbers.size(), false);
  for (int it = 0; it < 50; ++it) {
    for (int i = 0; i < numbers.size(); ++i) {
      if (y[numbers[i]] == 0) continue;
      if (finals[i]) continue;
      vector<int> units = gauss(basis, y[numbers[i]]);
      if (!success) {
        cout << -1;
        return 0;
      }
      int place = 0;
      while (place < units.size() && (units[place] == 0 || finals[place]))
        ++place;
      if (place == units.size()) continue;
      if (units[i]) place = i;
      if (i != place) {
        answer.push_back(make_pair(numbers[i], numbers[place]));
        answer.push_back(make_pair(numbers[place], numbers[i]));
        answer.push_back(make_pair(numbers[i], numbers[place]));
        swap(basis[i], basis[place]);
      }
      for (int j = 0; j < units.size(); ++j)
        if (units[j] && j != i && j != place) {
          basis[i] ^= basis[j];
          answer.push_back(make_pair(numbers[i], numbers[j]));
        }
      finals[i] = true;
    }
  }
  for (int i = 0; i < numbers.size(); ++i) {
    if (finals[i]) continue;
    if (y[numbers[i]] == 0) {
      answer.push_back(make_pair(numbers[i], numbers[i]));
      basis[i] = 0;
      continue;
    }
    vector<int> units = gauss(basis, y[numbers[i]]);
    if (!success) {
      cout << -1;
      return 0;
    }
    if (!units[i]) answer.push_back(make_pair(numbers[i], numbers[i]));
    for (int j = 0; j < numbers.size(); ++j) {
      if (j == i || !units[j]) continue;
      answer.push_back(make_pair(numbers[i], numbers[j]));
      basis[i] ^= basis[j];
    }
  }
  cout << answer.size() << "\n";
  for (int i = 0; i < answer.size(); ++i)
    cout << answer[i].first + 1 << " " << answer[i].second + 1 << "\n";
  return 0;
}