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>
const int MAXN = 10005;
int n;
unsigned x[MAXN];
unsigned y[MAXN];
int baseid[32];
std::bitset<32> base[32];
int basex[32];
std::bitset<32> yy[MAXN];
int nosol;
std::vector<std::pair<int, int> > ans;
std::vector<std::pair<int, int> > ans2;
void input() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) scanf("%u", &x[i]);
  for (int i = 0; i < n; ++i) scanf("%u", &y[i]);
}
void init() {
  memset(basex, -1, sizeof(basex));
  for (int i = 0; i < n; ++i) {
    int p = x[i];
    std::bitset<32> tmp;
    for (int j = 0; j < 32; ++j)
      if ((p >> j) & 1) {
        if (basex[j] != -1)
          p ^= basex[j], tmp ^= base[j];
        else {
          baseid[j] = i;
          base[j] = tmp;
          base[j][j] = 1;
          basex[j] = p;
          break;
        }
      }
  }
  for (int i = 0; i < n; ++i) {
    int p = y[i];
    for (int j = 0; j < 32; ++j)
      if ((p >> j) & 1) {
        if (basex[j] != -1)
          p ^= basex[j], yy[i] ^= base[j];
        else {
          nosol = 1;
          break;
        }
      }
  }
}
void solve() {
  if (nosol) {
    printf("-1\n");
    return;
  }
  for (int i = 0; i < n; ++i) {
    int fl = 1;
    for (int j = 0; j < 32; ++j)
      if (basex[j] != -1 && baseid[j] == i) {
        fl = 0;
        break;
      }
    if (fl) {
      ans.push_back(std::make_pair(i, i));
      for (int j = 0; j < 32; ++j)
        if (yy[i][j]) ans.push_back(std::make_pair(i, baseid[j]));
    }
  }
  int csl[32];
  int cpos[32];
  std::bitset<32> cc[32];
  int ccn = 0;
  for (int i = 0; i < 32; ++i)
    if (basex[i] != -1) {
      int u = baseid[i];
      csl[ccn] = i;
      cpos[ccn] = u;
      cc[ccn++] = yy[u];
    }
  for (int i = 0; i < ccn; ++i) {
    int r = -1;
    for (int j = i; j < ccn; ++j)
      if (cc[j][csl[i]]) {
        r = j;
        break;
      }
    if (r == -1) continue;
    if (r != i) {
      ans2.push_back(std::make_pair(cpos[r], cpos[i]));
      ans2.push_back(std::make_pair(cpos[i], cpos[r]));
      ans2.push_back(std::make_pair(cpos[r], cpos[i]));
      std::bitset<32> tmp = cc[i];
      cc[i] = cc[r];
      cc[r] = tmp;
    }
    for (int j = 0; j < ccn; ++j)
      if (j != i && cc[j][csl[i]]) {
        ans2.push_back(std::make_pair(cpos[j], cpos[i]));
        cc[j] ^= cc[i];
      }
  }
  for (int i = 0; i < ccn; ++i)
    if (cc[i][csl[i]] == 0) {
      for (int j = 0; j < i; ++j)
        if (cc[j][csl[i]]) ans.push_back(std::make_pair(cpos[j], cpos[i]));
      ans.push_back(std::make_pair(cpos[i], cpos[i]));
    }
  printf("%d\n", (int)ans.size() + (int)ans2.size());
  for (std::vector<std::pair<int, int> >::const_iterator i = ans.begin();
       i != ans.end(); ++i)
    printf("%d %d\n", i->first + 1, i->second + 1);
  for (std::vector<std::pair<int, int> >::const_reverse_iterator i =
           ans2.rbegin();
       i != ans2.rend(); ++i)
    printf("%d %d\n", i->first + 1, i->second + 1);
}
int main() {
  input();
  init();
  solve();
  return 0;
}