#include <bits/stdc++.h>
using namespace std;
#pragma comment(linker, "/STACK:255000000")
bool firstout = 1;
template <class T>
T &minn(T &a, T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
T &maxx(T &a, T b) {
  if (a < b) a = b;
  return a;
}
int &madd(int &a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
int &msub(int &a, int b) {
  a -= b;
  if (a < 0) a += 1000000007;
  return a;
}
int &mmult(int &a, int b) { return a = (long long)a * b % 1000000007; }
int mdiv(long long a, long long b, long long m) {
  a = (a % m + m) % m;
  b = (b % m + m) % m;
  if (a % b == 0) return a / b;
  return (a + m * mdiv(-a, m, b)) / b;
}
int n, m, q;
int X[10123], Y[10123];
int A[30][10123];
int P[30];
vector<pair<int, int> > ans;
int mask;
int oddb(int a) {
  int res = 0;
  for (; a; a &= a - 1) res ^= 1;
  return res;
}
void mkswap(int i, int j) {
  if (i == j) return;
  ans.push_back(make_pair(i, j));
  ans.push_back(make_pair(j, i));
  ans.push_back(make_pair(i, j));
}
void con() {
  if (mask == (1 << m) - 1) return;
  int i, j, k;
  for (i = (0); i < (m); ++i)
    if (Y[P[i]]) break;
  if (i == m) {
    for (i = (0); i < (m); ++i)
      if (mask >> i & 1 ^ 1) {
        ans.push_back(make_pair(P[i], P[i]));
      }
    return;
  }
  int a = Y[P[i]];
  for (j = (0); j < (m); ++j)
    if (a >> j & 1) break;
  mkswap(P[i], P[j]);
  swap(P[i], P[j]);
  i = j;
  for (j = (0); j < (m); ++j)
    if (i != j && a >> j & 1) ans.push_back(make_pair(P[i], P[j]));
  vector<int> v;
  for (j = (0); j < (m); ++j)
    if (Y[P[j]] >> i & 1) {
      Y[P[j]] ^= a;
      if (j != i) v.push_back(P[j]);
    }
  mask |= 1 << i;
  i = P[i];
  con();
  for (k = (0); k < (v.size()); ++k) {
    j = v[k];
    ans.push_back(make_pair(j, i));
  }
}
int main() {
  int i, j, k;
  char c;
  int a, d;
  int ts;
  for (ts = 1; scanf("%"
                     "d",
                     &(n)) > 0;
       ++ts) {
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(X[i]));
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(Y[i]));
    for (i = (0); i < (30); ++i) {
      for (j = (0); j < (n); ++j) A[i][j] = X[j] >> i & 1;
      A[i][j] = 1 << i;
    }
    m = 0;
    for (i = (0); i < (30); ++i) {
      a = n;
      int ii = 0;
      for (k = (i); k < (30); ++k) {
        for (j = (0); j < (n); ++j)
          if (A[k][j]) break;
        if (j < a) a = j, ii = k;
      }
      if (a == n) break;
      P[m++] = a;
      for (j = (0); j < (n + 1); ++j) swap(A[i][j], A[ii][j]);
      for (k = (i + 1); k < (30); ++k)
        if (A[k][P[i]]) {
          for (j = (0); j < (n + 1); ++j) A[k][j] ^= A[i][j];
        }
    }
    for (j = (0); j < (n); ++j) {
      int a = Y[j];
      for (i = (30) - 1; i >= (m); --i)
        if (oddb(a & A[i][n])) break;
      if (i >= m) break;
      int &res = Y[j];
      res = 0;
      for (i = (m)-1; i >= (0); --i) {
        int r = oddb(a & A[i][n]);
        for (k = (i + 1); k < (m); ++k)
          if (A[i][P[k]]) r ^= res >> k & 1;
        res |= r << i;
      }
    }
    if (j < n)
      printf(
          "%"
          "d",
          (-1)),
          printf("\n"), firstout = 1;
    else {
      ans.clear();
      for (j = (0); j < (n); ++j) {
        for (i = (0); i < (m); ++i)
          if (P[i] == j) break;
        if (i == m) {
          ans.push_back(make_pair(j, j));
          for (i = (0); i < (m); ++i)
            if ((Y[j] >> i) & 1) ans.push_back(make_pair(j, P[i]));
        }
      }
      mask = 0;
      con();
      printf(
          "%"
          "d",
          (ans.size()));
      printf("\n"), firstout = 1;
      for (i = (0); i < (ans.size()); ++i)
        printf((firstout) ? "%"
                            "d"
                          : " %"
                            "d",
               (ans[i].first + 1)),
            firstout = 0,
            printf((firstout) ? "%"
                                "d"
                              : " %"
                                "d",
                   (ans[i].second + 1)),
            firstout = 0, printf("\n"), firstout = 1;
    }
  }
  return 0;
}

### Prompt

Please create a solution in Cpp 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;
#pragma comment(linker, "/STACK:255000000")
bool firstout = 1;
template <class T>
T &minn(T &a, T b) {
  if (b < a) a = b;
  return a;
}
template <class T>
T &maxx(T &a, T b) {
  if (a < b) a = b;
  return a;
}
int &madd(int &a, int b) {
  a += b;
  if (a >= 1000000007) a -= 1000000007;
  return a;
}
int &msub(int &a, int b) {
  a -= b;
  if (a < 0) a += 1000000007;
  return a;
}
int &mmult(int &a, int b) { return a = (long long)a * b % 1000000007; }
int mdiv(long long a, long long b, long long m) {
  a = (a % m + m) % m;
  b = (b % m + m) % m;
  if (a % b == 0) return a / b;
  return (a + m * mdiv(-a, m, b)) / b;
}
int n, m, q;
int X[10123], Y[10123];
int A[30][10123];
int P[30];
vector<pair<int, int> > ans;
int mask;
int oddb(int a) {
  int res = 0;
  for (; a; a &= a - 1) res ^= 1;
  return res;
}
void mkswap(int i, int j) {
  if (i == j) return;
  ans.push_back(make_pair(i, j));
  ans.push_back(make_pair(j, i));
  ans.push_back(make_pair(i, j));
}
void con() {
  if (mask == (1 << m) - 1) return;
  int i, j, k;
  for (i = (0); i < (m); ++i)
    if (Y[P[i]]) break;
  if (i == m) {
    for (i = (0); i < (m); ++i)
      if (mask >> i & 1 ^ 1) {
        ans.push_back(make_pair(P[i], P[i]));
      }
    return;
  }
  int a = Y[P[i]];
  for (j = (0); j < (m); ++j)
    if (a >> j & 1) break;
  mkswap(P[i], P[j]);
  swap(P[i], P[j]);
  i = j;
  for (j = (0); j < (m); ++j)
    if (i != j && a >> j & 1) ans.push_back(make_pair(P[i], P[j]));
  vector<int> v;
  for (j = (0); j < (m); ++j)
    if (Y[P[j]] >> i & 1) {
      Y[P[j]] ^= a;
      if (j != i) v.push_back(P[j]);
    }
  mask |= 1 << i;
  i = P[i];
  con();
  for (k = (0); k < (v.size()); ++k) {
    j = v[k];
    ans.push_back(make_pair(j, i));
  }
}
int main() {
  int i, j, k;
  char c;
  int a, d;
  int ts;
  for (ts = 1; scanf("%"
                     "d",
                     &(n)) > 0;
       ++ts) {
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(X[i]));
    for (i = (0); i < (n); ++i)
      scanf(
          "%"
          "d",
          &(Y[i]));
    for (i = (0); i < (30); ++i) {
      for (j = (0); j < (n); ++j) A[i][j] = X[j] >> i & 1;
      A[i][j] = 1 << i;
    }
    m = 0;
    for (i = (0); i < (30); ++i) {
      a = n;
      int ii = 0;
      for (k = (i); k < (30); ++k) {
        for (j = (0); j < (n); ++j)
          if (A[k][j]) break;
        if (j < a) a = j, ii = k;
      }
      if (a == n) break;
      P[m++] = a;
      for (j = (0); j < (n + 1); ++j) swap(A[i][j], A[ii][j]);
      for (k = (i + 1); k < (30); ++k)
        if (A[k][P[i]]) {
          for (j = (0); j < (n + 1); ++j) A[k][j] ^= A[i][j];
        }
    }
    for (j = (0); j < (n); ++j) {
      int a = Y[j];
      for (i = (30) - 1; i >= (m); --i)
        if (oddb(a & A[i][n])) break;
      if (i >= m) break;
      int &res = Y[j];
      res = 0;
      for (i = (m)-1; i >= (0); --i) {
        int r = oddb(a & A[i][n]);
        for (k = (i + 1); k < (m); ++k)
          if (A[i][P[k]]) r ^= res >> k & 1;
        res |= r << i;
      }
    }
    if (j < n)
      printf(
          "%"
          "d",
          (-1)),
          printf("\n"), firstout = 1;
    else {
      ans.clear();
      for (j = (0); j < (n); ++j) {
        for (i = (0); i < (m); ++i)
          if (P[i] == j) break;
        if (i == m) {
          ans.push_back(make_pair(j, j));
          for (i = (0); i < (m); ++i)
            if ((Y[j] >> i) & 1) ans.push_back(make_pair(j, P[i]));
        }
      }
      mask = 0;
      con();
      printf(
          "%"
          "d",
          (ans.size()));
      printf("\n"), firstout = 1;
      for (i = (0); i < (ans.size()); ++i)
        printf((firstout) ? "%"
                            "d"
                          : " %"
                            "d",
               (ans[i].first + 1)),
            firstout = 0,
            printf((firstout) ? "%"
                                "d"
                              : " %"
                                "d",
                   (ans[i].second + 1)),
            firstout = 0, printf("\n"), firstout = 1;
    }
  }
  return 0;
}

```