#include <bits/stdc++.h>
using namespace std;
using vi = vector<long long>;
template <typename T>
std::istream& operator>>(std::istream& input, std::pair<T, T>& data) {
  input >> data.first >> data.second;
  return input;
}
template <typename T>
std::istream& operator>>(std::istream& input, std::vector<T>& data) {
  for (T& first : data) input >> first;
  return input;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const pair<T, T>& data) {
  output << "(" << data.first << "," << data.second << ")";
  return output;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const std::vector<T>& data) {
  for (const T& first : data) output << first << " ";
  return output;
}
std::ostream& operator<<(std::ostream& output, const __int128& first) {
  __int128 n = first;
  if (n == 0) {
    output << "0";
    return output;
  }
  if (n < 0) {
    n = -n;
    output << "-";
  }
  string s;
  while (n) {
    s += '0' + (n % 10);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  cout << s;
  return output;
}
long long div_up(long long a, long long b) {
  return a / b + ((a ^ b) > 0 && a % b);
}
long long div_down(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
long long math_mod(long long a, long long b) { return a - b * div_down(a, b); }
template <class T>
using V = vector<T>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    tie(a, b) = make_pair(b, a % b);
  }
  return a;
}
long long Bit(long long mask, long long bit) { return (mask >> bit) & 1; }
long long n;
const long long L = 30;
bool can_make(vi a, long long first) {
  for (long long i = (0); i < (L); ++i) {
    if (Bit(first, i)) {
      if (!a[i]) {
        return 0;
      }
      first ^= a[i];
    }
  }
  assert(first == 0);
  return 1;
}
pair<vi, V<pair<long long, long long> > > get(vi& a) {
  vi ans(L, -1);
  V<pair<long long, long long> > op;
  for (long long i = (0); i < (n); ++i) {
    for (long long bit = (0); bit < (L); ++bit) {
      if (Bit(a[i], bit)) {
        if (ans[bit] == -1) {
          ans[bit] = i;
          break;
        } else {
          op.push_back(make_pair(i, ans[bit]));
          a[i] ^= a[ans[bit]];
        }
      }
    }
  }
  return make_pair(ans, op);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vi a(n), b(n);
  cin >> a >> b;
  vi who_a, who_b;
  V<pair<long long, long long> > l, r;
  tie(who_a, l) = get(a);
  tie(who_b, r) = get(b);
  vi A_basis(L);
  for (long long i = (0); i < (L); ++i) {
    if (who_a[i] != -1) {
      A_basis[i] = a[who_a[i]];
    }
  }
  for (auto& e : b) {
    if (!can_make(A_basis, e)) {
      cout << -1 << '\n';
      exit(0);
    }
  }
  auto get_bit = [&](long long pos) {
    for (long long i = (0); i < (L); ++i) {
      if (who_a[i] == pos) {
        return i;
      }
    }
    return -1ll;
  };
  V<pair<long long, long long> > ans = l;
  auto make_swap = [&](long long i, long long j) {
    swap(a[i], a[j]);
    ans.push_back(make_pair(i, j));
    ans.push_back(make_pair(j, i));
    ans.push_back(make_pair(i, j));
  };
  vi need(n);
  for (long long bit = (0); bit < (L); ++bit) {
    if (who_b[bit] != -1) {
      assert(who_a[bit] != -1);
      long long pos = who_b[bit];
      need[pos] = 1;
      if (get_bit(pos) == bit) {
      } else if (get_bit(pos) == -1) {
        make_swap(pos, who_a[bit]);
        who_a[bit] = pos;
      } else {
        make_swap(pos, who_a[bit]);
        swap(who_a[get_bit(pos)], who_a[bit]);
      }
      long long want = b[pos] ^ a[pos];
      for (long long i = bit + 1; i < L; ++i) {
        if (Bit(want, i)) {
          assert(who_a[i] != -1);
          want ^= a[who_a[i]];
          ans.push_back(make_pair(pos, who_a[i]));
        }
      }
      assert(want == 0);
    }
  }
  for (long long i = (0); i < (n); ++i) {
    if (!need[i]) {
      ans.push_back(make_pair(i, i));
    }
  }
  reverse(r.begin(), r.end());
  for (auto& e : r) {
    ans.push_back(e);
  }
  cout << ans.size() << '\n';
  for (auto& e : ans) {
    cout << e.first + 1 << ' ' << e.second + 1 << '\n';
  }
}

### Prompt

Please provide a cpp coded solution 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;
using vi = vector<long long>;
template <typename T>
std::istream& operator>>(std::istream& input, std::pair<T, T>& data) {
  input >> data.first >> data.second;
  return input;
}
template <typename T>
std::istream& operator>>(std::istream& input, std::vector<T>& data) {
  for (T& first : data) input >> first;
  return input;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const pair<T, T>& data) {
  output << "(" << data.first << "," << data.second << ")";
  return output;
}
template <typename T>
std::ostream& operator<<(std::ostream& output, const std::vector<T>& data) {
  for (const T& first : data) output << first << " ";
  return output;
}
std::ostream& operator<<(std::ostream& output, const __int128& first) {
  __int128 n = first;
  if (n == 0) {
    output << "0";
    return output;
  }
  if (n < 0) {
    n = -n;
    output << "-";
  }
  string s;
  while (n) {
    s += '0' + (n % 10);
    n /= 10;
  }
  reverse(s.begin(), s.end());
  cout << s;
  return output;
}
long long div_up(long long a, long long b) {
  return a / b + ((a ^ b) > 0 && a % b);
}
long long div_down(long long a, long long b) {
  return a / b - ((a ^ b) < 0 && a % b);
}
long long math_mod(long long a, long long b) { return a - b * div_down(a, b); }
template <class T>
using V = vector<T>;
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
long long gcd(long long a, long long b) {
  while (b) {
    tie(a, b) = make_pair(b, a % b);
  }
  return a;
}
long long Bit(long long mask, long long bit) { return (mask >> bit) & 1; }
long long n;
const long long L = 30;
bool can_make(vi a, long long first) {
  for (long long i = (0); i < (L); ++i) {
    if (Bit(first, i)) {
      if (!a[i]) {
        return 0;
      }
      first ^= a[i];
    }
  }
  assert(first == 0);
  return 1;
}
pair<vi, V<pair<long long, long long> > > get(vi& a) {
  vi ans(L, -1);
  V<pair<long long, long long> > op;
  for (long long i = (0); i < (n); ++i) {
    for (long long bit = (0); bit < (L); ++bit) {
      if (Bit(a[i], bit)) {
        if (ans[bit] == -1) {
          ans[bit] = i;
          break;
        } else {
          op.push_back(make_pair(i, ans[bit]));
          a[i] ^= a[ans[bit]];
        }
      }
    }
  }
  return make_pair(ans, op);
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n;
  vi a(n), b(n);
  cin >> a >> b;
  vi who_a, who_b;
  V<pair<long long, long long> > l, r;
  tie(who_a, l) = get(a);
  tie(who_b, r) = get(b);
  vi A_basis(L);
  for (long long i = (0); i < (L); ++i) {
    if (who_a[i] != -1) {
      A_basis[i] = a[who_a[i]];
    }
  }
  for (auto& e : b) {
    if (!can_make(A_basis, e)) {
      cout << -1 << '\n';
      exit(0);
    }
  }
  auto get_bit = [&](long long pos) {
    for (long long i = (0); i < (L); ++i) {
      if (who_a[i] == pos) {
        return i;
      }
    }
    return -1ll;
  };
  V<pair<long long, long long> > ans = l;
  auto make_swap = [&](long long i, long long j) {
    swap(a[i], a[j]);
    ans.push_back(make_pair(i, j));
    ans.push_back(make_pair(j, i));
    ans.push_back(make_pair(i, j));
  };
  vi need(n);
  for (long long bit = (0); bit < (L); ++bit) {
    if (who_b[bit] != -1) {
      assert(who_a[bit] != -1);
      long long pos = who_b[bit];
      need[pos] = 1;
      if (get_bit(pos) == bit) {
      } else if (get_bit(pos) == -1) {
        make_swap(pos, who_a[bit]);
        who_a[bit] = pos;
      } else {
        make_swap(pos, who_a[bit]);
        swap(who_a[get_bit(pos)], who_a[bit]);
      }
      long long want = b[pos] ^ a[pos];
      for (long long i = bit + 1; i < L; ++i) {
        if (Bit(want, i)) {
          assert(who_a[i] != -1);
          want ^= a[who_a[i]];
          ans.push_back(make_pair(pos, who_a[i]));
        }
      }
      assert(want == 0);
    }
  }
  for (long long i = (0); i < (n); ++i) {
    if (!need[i]) {
      ans.push_back(make_pair(i, i));
    }
  }
  reverse(r.begin(), r.end());
  for (auto& e : r) {
    ans.push_back(e);
  }
  cout << ans.size() << '\n';
  for (auto& e : ans) {
    cout << e.first + 1 << ' ' << e.second + 1 << '\n';
  }
}

```