#include <bits/stdc++.h>
using namespace std;
int lsb(int x) { return x & -x; }
int n;
vector<int> x, y;
vector<int> basisX, basisY;
bool comp(int a, int b) { return lsb(x[a]) < lsb(x[b]); }
vector<pair<int, int> > gauss() {
  vector<pair<int, int> > res;
  for (int i = 0; i < n; i++) {
    for (int j : basisX) {
      if (x[i] & lsb(x[j])) {
        x[i] ^= x[j], res.push_back(make_pair(i, j));
      }
    }
    if (!x[i]) continue;
    for (int j : basisX) {
      if (x[j] & lsb(x[i])) {
        x[j] ^= x[i], res.push_back(make_pair(j, i));
      }
    }
    basisX.push_back(i);
  }
  sort(basisX.begin(), basisX.end(), comp);
  return res;
}
vector<pair<int, int> > conv() {
  vector<pair<int, int> > res;
  while (basisY.size()) {
    while (basisX.size() && lsb(x[basisX[0]]) != lsb(y[basisY[0]])) {
      res.push_back(make_pair(basisX[0], basisX[0]));
      basisX.erase(basisX.begin());
    }
    if (!basisX.size()) printf("-1\n"), exit(0);
    for (int i : basisX) {
      if (i != basisX[0] && ((x[basisX[0]] ^ y[basisY[0]]) & lsb(x[i]))) {
        x[basisX[0]] ^= x[i];
        res.push_back(make_pair(basisX[0], i));
      }
    }
    if (x[basisX[0]] != y[basisY[0]]) printf("-1\n"), exit(0);
    if (basisX[0] != basisY[0]) {
      swap(x[basisX[0]], x[basisY[0]]);
      for (int& i : basisX)
        if (i == basisY[0]) i = basisX[0];
      res.push_back(make_pair(basisX[0], basisY[0]));
      res.push_back(make_pair(basisY[0], basisX[0]));
      res.push_back(make_pair(basisX[0], basisY[0]));
    }
    basisX.erase(basisX.begin());
    basisY.erase(basisY.begin());
  }
  for (int i : basisX) res.push_back(make_pair(i, i));
  return res;
}
int main() {
  scanf("%d", &n);
  x.resize(n);
  y.resize(n);
  for (int i = 0; i < n; i++) scanf("%d", &x[i]);
  for (int i = 0; i < n; i++) scanf("%d", &y[i]);
  vector<pair<int, int> > resX, resY, resC;
  for (int d = 0; d < 2; d++) {
    resX = gauss();
    swap(resX, resY);
    swap(x, y);
    swap(basisX, basisY);
  }
  resC = conv();
  printf("%d\n", resX.size() + resC.size() + resY.size());
  reverse(resY.begin(), resY.end());
  for (auto p : resX) printf("%d %d\n", p.first + 1, p.second + 1);
  for (auto p : resC) printf("%d %d\n", p.first + 1, p.second + 1);
  for (auto p : resY) printf("%d %d\n", p.first + 1, p.second + 1);
  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 lsb(int x) { return x & -x; }
int n;
vector<int> x, y;
vector<int> basisX, basisY;
bool comp(int a, int b) { return lsb(x[a]) < lsb(x[b]); }
vector<pair<int, int> > gauss() {
  vector<pair<int, int> > res;
  for (int i = 0; i < n; i++) {
    for (int j : basisX) {
      if (x[i] & lsb(x[j])) {
        x[i] ^= x[j], res.push_back(make_pair(i, j));
      }
    }
    if (!x[i]) continue;
    for (int j : basisX) {
      if (x[j] & lsb(x[i])) {
        x[j] ^= x[i], res.push_back(make_pair(j, i));
      }
    }
    basisX.push_back(i);
  }
  sort(basisX.begin(), basisX.end(), comp);
  return res;
}
vector<pair<int, int> > conv() {
  vector<pair<int, int> > res;
  while (basisY.size()) {
    while (basisX.size() && lsb(x[basisX[0]]) != lsb(y[basisY[0]])) {
      res.push_back(make_pair(basisX[0], basisX[0]));
      basisX.erase(basisX.begin());
    }
    if (!basisX.size()) printf("-1\n"), exit(0);
    for (int i : basisX) {
      if (i != basisX[0] && ((x[basisX[0]] ^ y[basisY[0]]) & lsb(x[i]))) {
        x[basisX[0]] ^= x[i];
        res.push_back(make_pair(basisX[0], i));
      }
    }
    if (x[basisX[0]] != y[basisY[0]]) printf("-1\n"), exit(0);
    if (basisX[0] != basisY[0]) {
      swap(x[basisX[0]], x[basisY[0]]);
      for (int& i : basisX)
        if (i == basisY[0]) i = basisX[0];
      res.push_back(make_pair(basisX[0], basisY[0]));
      res.push_back(make_pair(basisY[0], basisX[0]));
      res.push_back(make_pair(basisX[0], basisY[0]));
    }
    basisX.erase(basisX.begin());
    basisY.erase(basisY.begin());
  }
  for (int i : basisX) res.push_back(make_pair(i, i));
  return res;
}
int main() {
  scanf("%d", &n);
  x.resize(n);
  y.resize(n);
  for (int i = 0; i < n; i++) scanf("%d", &x[i]);
  for (int i = 0; i < n; i++) scanf("%d", &y[i]);
  vector<pair<int, int> > resX, resY, resC;
  for (int d = 0; d < 2; d++) {
    resX = gauss();
    swap(resX, resY);
    swap(x, y);
    swap(basisX, basisY);
  }
  resC = conv();
  printf("%d\n", resX.size() + resC.size() + resY.size());
  reverse(resY.begin(), resY.end());
  for (auto p : resX) printf("%d %d\n", p.first + 1, p.second + 1);
  for (auto p : resC) printf("%d %d\n", p.first + 1, p.second + 1);
  for (auto p : resY) printf("%d %d\n", p.first + 1, p.second + 1);
  return 0;
}

```