#include <bits/stdc++.h>
using namespace std;
int MODP(long long x) {
  int r = x % 1000000007;
  if (r < 0) r += 1000000007;
  return r;
}
class AbstractGF2MatrixRecorder {
 public:
  virtual void record(int r1, int r2) {}
  virtual void recordSwap(int r1, int r2) {}
};
class GF2MatrixRecorder : public AbstractGF2MatrixRecorder {
  vector<pair<int, int>> op;

 public:
  void record(int r1, int r2) { op.emplace_back(r1, r2); }
  void recordSwap(int r1, int r2) {
    if (r1 == r2) return;
    op.emplace_back(r1, r2);
    op.emplace_back(r2, r1);
    op.emplace_back(r1, r2);
  }
  const vector<pair<int, int>> &getOperations() { return op; }
};
template <int NCOL>
class GF2Matrix {
  vector<bitset<NCOL>> row;
  int nRow;
  vector<int> order;
  vector<size_t> length;
  bool isLock;
  int rank;
  bool gaussianEliminationCalled;
  vector<int> first1;
  AbstractGF2MatrixRecorder noRecorder;
  AbstractGF2MatrixRecorder &recorder;

 public:
  GF2Matrix(int nRow) : recorder(noRecorder) { init(nRow); }
  GF2Matrix(int nRow, AbstractGF2MatrixRecorder &recorder)
      : recorder(recorder) {
    init(nRow);
  }
  int numRow() const { return nRow; }
  int numCol() const { return NCOL; }
  void init(int nRow) {
    this->nRow = nRow;
    row.resize(nRow);
    order.resize(nRow);
    for (auto r = 0; r < nRow; ++r) {
      order[r] = r;
    }
    length.resize(nRow);
    isLock = false;
    gaussianEliminationCalled = false;
  }
  void setRow(int r, const bitset<NCOL> &rV) { row[r] = rV; }
  void lock() {
    isLock = true;
    for (auto r = 0; r < nRow; ++r) {
      for (auto c = NCOL - 1; c >= 0; --c) {
        if (row[r].test(c)) {
          length[r] = c;
          break;
        }
      }
    }
  }
  void gaussianElimination() {
    assert(isLock);
    first1.resize(nRow);
    rank = 0;
    for (int c = NCOL - 1, r = 0; c >= 0; c--) {
      int i = r;
      while (i < nRow && !getRow(i).test(c)) {
        ++i;
      }
      if (i >= nRow) {
        continue;
      }
      first1[r] = c;
      swap(order[r], order[i]);
      recorder.recordSwap(r, i);
      for (auto j = 0; j < nRow; ++j) {
        if (j != r && getRow(j).test(c)) {
          recorder.record(j, r);
          row[order[j]] ^= getRow(r);
        }
      }
      r++;
      rank++;
    }
    gaussianEliminationCalled = true;
  }
  int getFirst1(int row) const {
    assert(gaussianEliminationCalled);
    assert(row < rank);
    return first1[row];
  }
  void transform(const GF2Matrix<NCOL> &t) {
    assert(t.isGaussianEliminationCalled());
    for (auto r = 0; r < rank; ++r) {
      int c = getFirst1(r);
      for (auto r2 = 0; r2 < rank; ++r2) {
        if (getRow(r2).test(c) != t.getRow(r2).test(c)) {
          row[order[r2]] ^= getRow(r);
          recorder.record(r2, r);
        }
      }
    }
  }
  bool isGaussianEliminationCalled() const { return gaussianEliminationCalled; }
  int getRank() const {
    assert(gaussianEliminationCalled);
    return rank;
  }
  inline const bitset<NCOL> &getRow(int r) const { return row[order[r]]; }
  bool operator==(const GF2Matrix<NCOL> &y) const {
    if (y.numRow() != numRow()) return false;
    for (auto r = 0; r < nRow; ++r) {
      if (getRow(r) != y.getRow(r)) return false;
    }
    return true;
  }
  friend std::ostream &operator<<(std::ostream &stream,
                                  const GF2Matrix<NCOL> &matrix) {
    stream << "[matrix: row = " << matrix.nRow << ", col = " << NCOL << endl;
    for (auto r = 0; r < matrix.nRow; ++r) {
      for (auto c = NCOL - 1; c >= 0; --c) {
        stream << matrix.getRow(r).test(c) << " ";
      }
      stream << endl;
    }
    stream << "]" << endl;
    return stream;
  }
};
void testGen() {
  freopen("biginput1.txt", "w", stdout);
  fclose(stdout);
}
void output(const GF2Matrix<32> &a) {
  ostringstream ss;
  for (auto r = 0; r < a.numRow(); ++r) {
    ss << a.getRow(r).to_ullong() << " ";
  }
  if (1 <= 0) cout << "[LOG " << 0 << "] " << ss.str() << endl;
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> initial;
  GF2MatrixRecorder recordA, recordT;
  GF2Matrix<32> a(n, recordA);
  for (auto r = 0; r < n; ++r) {
    int x;
    cin >> x;
    initial.push_back(x);
    a.setRow(r, x);
  }
  a.lock();
  a.gaussianElimination();
  vector<int> target;
  for (auto repeat_var = 0; repeat_var < n; ++repeat_var) {
    int x;
    cin >> x;
    target.push_back(x);
  }
  GF2Matrix<32> b(2 * n);
  for (auto r = 0; r < n; ++r) {
    b.setRow(r, a.getRow(r));
  }
  int r = n;
  for (int x : target) {
    b.setRow(r, x);
    r++;
  }
  b.lock();
  b.gaussianElimination();
  if (b.getRank() != a.getRank()) {
    cout << -1 << endl;
  } else {
    GF2Matrix<32> t(n, recordT);
    for (auto r = 0; r < n; ++r) {
      t.setRow(r, target[r]);
    }
    t.lock();
    t.gaussianElimination();
    a.transform(t);
    vector<pair<int, int>> ret;
    for (auto p : recordA.getOperations()) {
      ret.push_back(p);
    }
    for (auto it = recordT.getOperations().rbegin();
         it != recordT.getOperations().rend(); ++it) {
      ret.push_back(*it);
    }
    cout << ret.size() << endl;
    for (auto p : ret) {
      cout << p.first + 1 << " " << p.second + 1 << " " << endl;
      initial[p.first] ^= initial[p.second];
    }
    for (auto i = 0; i < n; ++i) {
      if (1 <= 0) cout << "[LOG " << 0 << "] " << initial[i] << endl;
    }
  }
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int MODP(long long x) {
  int r = x % 1000000007;
  if (r < 0) r += 1000000007;
  return r;
}
class AbstractGF2MatrixRecorder {
 public:
  virtual void record(int r1, int r2) {}
  virtual void recordSwap(int r1, int r2) {}
};
class GF2MatrixRecorder : public AbstractGF2MatrixRecorder {
  vector<pair<int, int>> op;

 public:
  void record(int r1, int r2) { op.emplace_back(r1, r2); }
  void recordSwap(int r1, int r2) {
    if (r1 == r2) return;
    op.emplace_back(r1, r2);
    op.emplace_back(r2, r1);
    op.emplace_back(r1, r2);
  }
  const vector<pair<int, int>> &getOperations() { return op; }
};
template <int NCOL>
class GF2Matrix {
  vector<bitset<NCOL>> row;
  int nRow;
  vector<int> order;
  vector<size_t> length;
  bool isLock;
  int rank;
  bool gaussianEliminationCalled;
  vector<int> first1;
  AbstractGF2MatrixRecorder noRecorder;
  AbstractGF2MatrixRecorder &recorder;

 public:
  GF2Matrix(int nRow) : recorder(noRecorder) { init(nRow); }
  GF2Matrix(int nRow, AbstractGF2MatrixRecorder &recorder)
      : recorder(recorder) {
    init(nRow);
  }
  int numRow() const { return nRow; }
  int numCol() const { return NCOL; }
  void init(int nRow) {
    this->nRow = nRow;
    row.resize(nRow);
    order.resize(nRow);
    for (auto r = 0; r < nRow; ++r) {
      order[r] = r;
    }
    length.resize(nRow);
    isLock = false;
    gaussianEliminationCalled = false;
  }
  void setRow(int r, const bitset<NCOL> &rV) { row[r] = rV; }
  void lock() {
    isLock = true;
    for (auto r = 0; r < nRow; ++r) {
      for (auto c = NCOL - 1; c >= 0; --c) {
        if (row[r].test(c)) {
          length[r] = c;
          break;
        }
      }
    }
  }
  void gaussianElimination() {
    assert(isLock);
    first1.resize(nRow);
    rank = 0;
    for (int c = NCOL - 1, r = 0; c >= 0; c--) {
      int i = r;
      while (i < nRow && !getRow(i).test(c)) {
        ++i;
      }
      if (i >= nRow) {
        continue;
      }
      first1[r] = c;
      swap(order[r], order[i]);
      recorder.recordSwap(r, i);
      for (auto j = 0; j < nRow; ++j) {
        if (j != r && getRow(j).test(c)) {
          recorder.record(j, r);
          row[order[j]] ^= getRow(r);
        }
      }
      r++;
      rank++;
    }
    gaussianEliminationCalled = true;
  }
  int getFirst1(int row) const {
    assert(gaussianEliminationCalled);
    assert(row < rank);
    return first1[row];
  }
  void transform(const GF2Matrix<NCOL> &t) {
    assert(t.isGaussianEliminationCalled());
    for (auto r = 0; r < rank; ++r) {
      int c = getFirst1(r);
      for (auto r2 = 0; r2 < rank; ++r2) {
        if (getRow(r2).test(c) != t.getRow(r2).test(c)) {
          row[order[r2]] ^= getRow(r);
          recorder.record(r2, r);
        }
      }
    }
  }
  bool isGaussianEliminationCalled() const { return gaussianEliminationCalled; }
  int getRank() const {
    assert(gaussianEliminationCalled);
    return rank;
  }
  inline const bitset<NCOL> &getRow(int r) const { return row[order[r]]; }
  bool operator==(const GF2Matrix<NCOL> &y) const {
    if (y.numRow() != numRow()) return false;
    for (auto r = 0; r < nRow; ++r) {
      if (getRow(r) != y.getRow(r)) return false;
    }
    return true;
  }
  friend std::ostream &operator<<(std::ostream &stream,
                                  const GF2Matrix<NCOL> &matrix) {
    stream << "[matrix: row = " << matrix.nRow << ", col = " << NCOL << endl;
    for (auto r = 0; r < matrix.nRow; ++r) {
      for (auto c = NCOL - 1; c >= 0; --c) {
        stream << matrix.getRow(r).test(c) << " ";
      }
      stream << endl;
    }
    stream << "]" << endl;
    return stream;
  }
};
void testGen() {
  freopen("biginput1.txt", "w", stdout);
  fclose(stdout);
}
void output(const GF2Matrix<32> &a) {
  ostringstream ss;
  for (auto r = 0; r < a.numRow(); ++r) {
    ss << a.getRow(r).to_ullong() << " ";
  }
  if (1 <= 0) cout << "[LOG " << 0 << "] " << ss.str() << endl;
}
int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  vector<int> initial;
  GF2MatrixRecorder recordA, recordT;
  GF2Matrix<32> a(n, recordA);
  for (auto r = 0; r < n; ++r) {
    int x;
    cin >> x;
    initial.push_back(x);
    a.setRow(r, x);
  }
  a.lock();
  a.gaussianElimination();
  vector<int> target;
  for (auto repeat_var = 0; repeat_var < n; ++repeat_var) {
    int x;
    cin >> x;
    target.push_back(x);
  }
  GF2Matrix<32> b(2 * n);
  for (auto r = 0; r < n; ++r) {
    b.setRow(r, a.getRow(r));
  }
  int r = n;
  for (int x : target) {
    b.setRow(r, x);
    r++;
  }
  b.lock();
  b.gaussianElimination();
  if (b.getRank() != a.getRank()) {
    cout << -1 << endl;
  } else {
    GF2Matrix<32> t(n, recordT);
    for (auto r = 0; r < n; ++r) {
      t.setRow(r, target[r]);
    }
    t.lock();
    t.gaussianElimination();
    a.transform(t);
    vector<pair<int, int>> ret;
    for (auto p : recordA.getOperations()) {
      ret.push_back(p);
    }
    for (auto it = recordT.getOperations().rbegin();
         it != recordT.getOperations().rend(); ++it) {
      ret.push_back(*it);
    }
    cout << ret.size() << endl;
    for (auto p : ret) {
      cout << p.first + 1 << " " << p.second + 1 << " " << endl;
      initial[p.first] ^= initial[p.second];
    }
    for (auto i = 0; i < n; ++i) {
      if (1 <= 0) cout << "[LOG " << 0 << "] " << initial[i] << endl;
    }
  }
  return 0;
}

```