#include <bits/stdc++.h>
using namespace std;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
vector<pair<int, int>> v1, v2;
int a[10005], b[10005];
int gau(int a[], int n, vector<pair<int, int>> &v) {
  int j = 0;
  for (int i = 0; i < 30; i++) {
    int x = -1;
    for (int k = j; k < n; k++)
      if (a[k] & (1 << i)) {
        x = k;
        break;
      }
    if (x == -1) continue;
    if (x != j) {
      swap(a[x], a[j]);
      v.push_back({j, x});
      v.push_back({x, j});
      v.push_back({j, x});
    }
    for (int k = j + 1; k < n; k++)
      if (a[k] & (1 << i)) {
        a[k] ^= a[j];
        v.push_back({k, j});
      }
    j++;
  }
  return j;
}
int tmp[40], tmp2[40];
bool cal(int a[], int n, int val) {
  memset(tmp2, 0, sizeof tmp2);
  memset(tmp, 0, sizeof tmp);
  for (int(i) = 0; (i) < (int)(n); (i)++) {
    for (int(j) = 0; (j) < (int)(30); (j)++)
      if (a[i] & (1 << j)) {
        tmp2[j] |= (1 << i);
      }
  }
  for (int(j) = 0; (j) < (int)(30); (j)++)
    if (val & (1 << j)) {
      tmp2[j] |= (1 << n);
    }
  vector<pair<int, int>> gg;
  gau(tmp2, 30, gg);
  for (int i = 29; i >= 0; i--)
    if (tmp2[i]) {
      if (tmp2[i] == (1 << n)) return 0;
      int j = 0;
      while (!(tmp2[i] & (1 << j))) j++;
      tmp[j] = (tmp2[i] & (1 << n)) ? 1 : 0;
      for (int k = j + 1; k < n; k++)
        if (tmp2[i] & (1 << k)) {
          tmp[j] ^= tmp[k];
        }
    }
  return 1;
}
int main() {
  scanf("%d", &n);
  for (int(i) = 0; (i) < (int)(n); (i)++) scanf("%d", a + i);
  for (int(i) = 0; (i) < (int)(n); (i)++) scanf("%d", b + i);
  int x = gau(a, n, v1);
  int y = gau(b, n, v2);
  for (int i = x; i < n; i++) assert(a[i] == 0);
  for (int i = y; i < n; i++) assert(b[i] == 0);
  reverse(v2.begin(), v2.end());
  for (int(i) = 0; (i) < (int)(y); (i)++) {
    if (!cal(a, x, b[i])) {
      puts("-1");
      return 0;
    }
    if (tmp[i] == 0) {
      for (int j = i + 1; j < x; j++)
        if (tmp[j]) {
          swap(tmp[i], tmp[j]);
          swap(a[i], a[j]);
          v1.push_back({i, j});
          v1.push_back({j, i});
          v1.push_back({i, j});
          break;
        }
    }
    tmp[i] = 0;
    for (int(j) = 0; (j) < (int)(x); (j)++)
      if (tmp[j]) {
        a[i] ^= a[j];
        v1.push_back({i, j});
      }
  }
  for (int i = y; i < x; i++) {
    v1.push_back({i, i});
  }
  printf("%d\n", v1.size() + v2.size());
  for (auto p : v1) {
    printf("%d %d\n", p.first + 1, p.second + 1);
    a[p.first] ^= a[p.second];
  }
  for (auto p : v2) {
    printf("%d %d\n", p.first + 1, p.second + 1);
    a[p.first] ^= a[p.second];
  }
  return 0;
}

### Prompt

Please formulate a cpp solution to the following 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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool debug = 1;
int n, m, k;
int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};
long long ln, lk, lm;
vector<pair<int, int>> v1, v2;
int a[10005], b[10005];
int gau(int a[], int n, vector<pair<int, int>> &v) {
  int j = 0;
  for (int i = 0; i < 30; i++) {
    int x = -1;
    for (int k = j; k < n; k++)
      if (a[k] & (1 << i)) {
        x = k;
        break;
      }
    if (x == -1) continue;
    if (x != j) {
      swap(a[x], a[j]);
      v.push_back({j, x});
      v.push_back({x, j});
      v.push_back({j, x});
    }
    for (int k = j + 1; k < n; k++)
      if (a[k] & (1 << i)) {
        a[k] ^= a[j];
        v.push_back({k, j});
      }
    j++;
  }
  return j;
}
int tmp[40], tmp2[40];
bool cal(int a[], int n, int val) {
  memset(tmp2, 0, sizeof tmp2);
  memset(tmp, 0, sizeof tmp);
  for (int(i) = 0; (i) < (int)(n); (i)++) {
    for (int(j) = 0; (j) < (int)(30); (j)++)
      if (a[i] & (1 << j)) {
        tmp2[j] |= (1 << i);
      }
  }
  for (int(j) = 0; (j) < (int)(30); (j)++)
    if (val & (1 << j)) {
      tmp2[j] |= (1 << n);
    }
  vector<pair<int, int>> gg;
  gau(tmp2, 30, gg);
  for (int i = 29; i >= 0; i--)
    if (tmp2[i]) {
      if (tmp2[i] == (1 << n)) return 0;
      int j = 0;
      while (!(tmp2[i] & (1 << j))) j++;
      tmp[j] = (tmp2[i] & (1 << n)) ? 1 : 0;
      for (int k = j + 1; k < n; k++)
        if (tmp2[i] & (1 << k)) {
          tmp[j] ^= tmp[k];
        }
    }
  return 1;
}
int main() {
  scanf("%d", &n);
  for (int(i) = 0; (i) < (int)(n); (i)++) scanf("%d", a + i);
  for (int(i) = 0; (i) < (int)(n); (i)++) scanf("%d", b + i);
  int x = gau(a, n, v1);
  int y = gau(b, n, v2);
  for (int i = x; i < n; i++) assert(a[i] == 0);
  for (int i = y; i < n; i++) assert(b[i] == 0);
  reverse(v2.begin(), v2.end());
  for (int(i) = 0; (i) < (int)(y); (i)++) {
    if (!cal(a, x, b[i])) {
      puts("-1");
      return 0;
    }
    if (tmp[i] == 0) {
      for (int j = i + 1; j < x; j++)
        if (tmp[j]) {
          swap(tmp[i], tmp[j]);
          swap(a[i], a[j]);
          v1.push_back({i, j});
          v1.push_back({j, i});
          v1.push_back({i, j});
          break;
        }
    }
    tmp[i] = 0;
    for (int(j) = 0; (j) < (int)(x); (j)++)
      if (tmp[j]) {
        a[i] ^= a[j];
        v1.push_back({i, j});
      }
  }
  for (int i = y; i < x; i++) {
    v1.push_back({i, i});
  }
  printf("%d\n", v1.size() + v2.size());
  for (auto p : v1) {
    printf("%d %d\n", p.first + 1, p.second + 1);
    a[p.first] ^= a[p.second];
  }
  for (auto p : v2) {
    printf("%d %d\n", p.first + 1, p.second + 1);
    a[p.first] ^= a[p.second];
  }
  return 0;
}

```