#include <bits/stdc++.h>
using std::cin;
using std::complex;
using std::cout;
using std::endl;
using std::fixed;
using std::greater;
using std::ios_base;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multiset;
using std::next_permutation;
using std::ostream;
using std::pair;
using std::prev_permutation;
using std::random_shuffle;
using std::reverse;
using std::set;
using std::setprecision;
using std::sort;
using std::string;
using std::swap;
using std::upper_bound;
using std::vector;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
vector<pair<long long, long long> > ans[2];
const long long N = 1e5 + 5;
long long x[N];
long long y[N];
long long z[N];
long long goal[N];
long long fix[N];
long long Magic(long long n) { return n - (n & (n - 1)); }
map<long long, long long> where_fir_x;
map<long long, long long> where_fir_y;
void Xor(long long i, long long j, long long which) {
  if (j == 0) {
    cout << "-1\n";
    exit(0);
  }
  if (which == 0) {
    x[i] ^= x[j];
  } else {
    y[i] ^= y[j];
  }
  ans[which].push_back(make_pair(i, j));
}
void Swap(long long i, long long j, long long which) {
  if (i == j) {
    return;
  }
  Xor(i, j, which);
  Xor(j, i, which);
  Xor(i, j, which);
}
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  long long n;
  cin >> n;
  ;
  for (long long i = (1); i <= (n); ++i) {
    cin >> x[i];
    z[i] = x[i];
  }
  for (long long i = (1); i <= (n); ++i) {
    cin >> y[i];
    goal[i] = y[i];
  }
  long long pot = 1;
  long long st_x = 1;
  while (pot < (1 << 30)) {
    bool got = false;
    for (long long i = st_x; i <= n; i++) {
      if (x[i] & pot) {
        Swap(i, st_x, 0);
        got = true;
        break;
      }
    }
    if (got) {
      for (long long i = 1; i <= n; i++) {
        if (i != st_x && (x[i] & pot)) {
          Xor(i, st_x, 0);
        }
      }
      where_fir_x[pot] = st_x;
      st_x++;
    }
    pot *= 2;
  }
  for (long long i = (1); i <= (n); ++i) {
    if (0) cout << x[i] << " ";
  }
  if (0) cout << endl;
  pot = 1;
  long long st_y = 1;
  while (pot < (1 << 30)) {
    bool got = false;
    for (long long i = st_y; i <= n; i++) {
      if (y[i] & pot) {
        Swap(i, st_y, 1);
        got = true;
        break;
      }
    }
    if (got) {
      for (long long i = 1; i <= n; i++) {
        if (i != st_y && (y[i] & pot)) {
          Xor(i, st_y, 1);
        }
      }
      where_fir_y[pot] = st_y;
      if (where_fir_x[pot] == 0) {
        cout << "-1\n";
        return 0;
      }
      st_y++;
    }
    pot *= 2;
  }
  if (0) cout << "Y\n";
  for (long long i = (1); i <= (n); ++i) {
    if (0) cout << y[i] << " ";
  }
  if (0) cout << endl;
  for (long long i = 1; i <= st_y - 1; i++) {
    ;
    long long want = y[i];
    vector<long long> want_x;
    while (want) {
      long long ind = 0;
      for (long long j = st_x - 1; j >= 1; j--) {
        if (Magic(x[j]) == Magic(want)) {
          ind = j;
          break;
        }
      }
      if (ind == 0) {
        cout << "-1\n";
        if (0) cout << "Not in span\n";
        return 0;
      }
      want ^= x[ind];
      want_x.push_back(ind);
    }
    long long need_swap = 1;
    for (long long j = 0; j < want_x.size(); j++) {
      long long p = want_x[j];
      if (p == i) {
        need_swap = 0;
        swap(want_x[j], want_x.back());
        want_x.pop_back();
        break;
      }
    }
    if (need_swap) {
      swap(want_x[0], want_x.back());
      Swap(i, want_x.back(), 0);
      want_x.pop_back();
    }
    for (auto p : want_x) {
      Xor(i, p, 0);
    }
    assert(x[i] == y[i]);
    fix[i] = 1;
    if (0) cout << "Ustawiamy " << i << "\n";
    for (long long j = (1); j <= (n); ++j) {
      if (0) cout << x[j] << " ";
    }
    if (0) cout << endl;
  }
  for (long long i = (st_y); i <= (n); ++i) {
    Xor(i, i, 0);
  }
  reverse((ans[1]).begin(), (ans[1]).end());
  cout << ans[0].size() + ((long long)(ans[1]).size()) << endl;
  for (long long i = 0; i < (2); ++i) {
    for (auto p : ans[i]) {
      cout << p.first << " " << p.second << "\n";
      z[p.first] ^= z[p.second];
    }
  }
  for (long long i = (1); i <= (n); ++i) {
    assert(z[i] == goal[i]);
  }
  return 0;
}

### Prompt

In Cpp, your task is to solve 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 std::cin;
using std::complex;
using std::cout;
using std::endl;
using std::fixed;
using std::greater;
using std::ios_base;
using std::lower_bound;
using std::make_pair;
using std::map;
using std::max;
using std::min;
using std::multiset;
using std::next_permutation;
using std::ostream;
using std::pair;
using std::prev_permutation;
using std::random_shuffle;
using std::reverse;
using std::set;
using std::setprecision;
using std::sort;
using std::string;
using std::swap;
using std::upper_bound;
using std::vector;
template <class C>
void mini(C& a4, C b4) {
  a4 = min(a4, b4);
}
template <class C>
void maxi(C& a4, C b4) {
  a4 = max(a4, b4);
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> pair) {
  return out << "(" << pair.first << ", " << pair.second << ")";
}
vector<pair<long long, long long> > ans[2];
const long long N = 1e5 + 5;
long long x[N];
long long y[N];
long long z[N];
long long goal[N];
long long fix[N];
long long Magic(long long n) { return n - (n & (n - 1)); }
map<long long, long long> where_fir_x;
map<long long, long long> where_fir_y;
void Xor(long long i, long long j, long long which) {
  if (j == 0) {
    cout << "-1\n";
    exit(0);
  }
  if (which == 0) {
    x[i] ^= x[j];
  } else {
    y[i] ^= y[j];
  }
  ans[which].push_back(make_pair(i, j));
}
void Swap(long long i, long long j, long long which) {
  if (i == j) {
    return;
  }
  Xor(i, j, which);
  Xor(j, i, which);
  Xor(i, j, which);
}
int main() {
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(10);
  double beg_clock = 1.0 * clock() / CLOCKS_PER_SEC;
  long long n;
  cin >> n;
  ;
  for (long long i = (1); i <= (n); ++i) {
    cin >> x[i];
    z[i] = x[i];
  }
  for (long long i = (1); i <= (n); ++i) {
    cin >> y[i];
    goal[i] = y[i];
  }
  long long pot = 1;
  long long st_x = 1;
  while (pot < (1 << 30)) {
    bool got = false;
    for (long long i = st_x; i <= n; i++) {
      if (x[i] & pot) {
        Swap(i, st_x, 0);
        got = true;
        break;
      }
    }
    if (got) {
      for (long long i = 1; i <= n; i++) {
        if (i != st_x && (x[i] & pot)) {
          Xor(i, st_x, 0);
        }
      }
      where_fir_x[pot] = st_x;
      st_x++;
    }
    pot *= 2;
  }
  for (long long i = (1); i <= (n); ++i) {
    if (0) cout << x[i] << " ";
  }
  if (0) cout << endl;
  pot = 1;
  long long st_y = 1;
  while (pot < (1 << 30)) {
    bool got = false;
    for (long long i = st_y; i <= n; i++) {
      if (y[i] & pot) {
        Swap(i, st_y, 1);
        got = true;
        break;
      }
    }
    if (got) {
      for (long long i = 1; i <= n; i++) {
        if (i != st_y && (y[i] & pot)) {
          Xor(i, st_y, 1);
        }
      }
      where_fir_y[pot] = st_y;
      if (where_fir_x[pot] == 0) {
        cout << "-1\n";
        return 0;
      }
      st_y++;
    }
    pot *= 2;
  }
  if (0) cout << "Y\n";
  for (long long i = (1); i <= (n); ++i) {
    if (0) cout << y[i] << " ";
  }
  if (0) cout << endl;
  for (long long i = 1; i <= st_y - 1; i++) {
    ;
    long long want = y[i];
    vector<long long> want_x;
    while (want) {
      long long ind = 0;
      for (long long j = st_x - 1; j >= 1; j--) {
        if (Magic(x[j]) == Magic(want)) {
          ind = j;
          break;
        }
      }
      if (ind == 0) {
        cout << "-1\n";
        if (0) cout << "Not in span\n";
        return 0;
      }
      want ^= x[ind];
      want_x.push_back(ind);
    }
    long long need_swap = 1;
    for (long long j = 0; j < want_x.size(); j++) {
      long long p = want_x[j];
      if (p == i) {
        need_swap = 0;
        swap(want_x[j], want_x.back());
        want_x.pop_back();
        break;
      }
    }
    if (need_swap) {
      swap(want_x[0], want_x.back());
      Swap(i, want_x.back(), 0);
      want_x.pop_back();
    }
    for (auto p : want_x) {
      Xor(i, p, 0);
    }
    assert(x[i] == y[i]);
    fix[i] = 1;
    if (0) cout << "Ustawiamy " << i << "\n";
    for (long long j = (1); j <= (n); ++j) {
      if (0) cout << x[j] << " ";
    }
    if (0) cout << endl;
  }
  for (long long i = (st_y); i <= (n); ++i) {
    Xor(i, i, 0);
  }
  reverse((ans[1]).begin(), (ans[1]).end());
  cout << ans[0].size() + ((long long)(ans[1]).size()) << endl;
  for (long long i = 0; i < (2); ++i) {
    for (auto p : ans[i]) {
      cout << p.first << " " << p.second << "\n";
      z[p.first] ^= z[p.second];
    }
  }
  for (long long i = (1); i <= (n); ++i) {
    assert(z[i] == goal[i]);
  }
  return 0;
}

```