#include <bits/stdc++.h>
using namespace std;
namespace zyt {
template <typename T>
inline bool read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != EOF && c != '-' && !isdigit(c));
  if (c == EOF) return false;
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
  return true;
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 1e4 + 10, M = 1e6 + 10, B = 31;
bool check(const int a, const int p) { return a & (1 << p); }
class Linear_Basis {
 private:
  int a[B], b[B], msk[B];

 public:
  Linear_Basis() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(msk, 0, sizeof(msk));
  }
  bool insert(int x, const int id) {
    int m = 0;
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i], m ^= msk[i];
        else {
          a[i] = x, b[i] = id, msk[i] = (m ^ (1 << i));
          return true;
        }
      }
    return false;
  }
  bool query(int x) const {
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i];
        else
          return false;
      }
    return true;
  }
  bool query(int x, vector<int> &v) const {
    v.clear();
    int m = 0;
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i], m ^= msk[i];
        else
          return false;
      }
    for (int i = 0; i < B; i++)
      if (check(m, i)) v.push_back(b[i]);
    return true;
  }
};
int n, x[N], y[N], cnt, id[N];
pair<int, int> ans[M];
Linear_Basis a, b;
void swp(const int a, const int b) {
  if (a == b) return;
  ans[cnt++] = pair<int, int>(a, b);
  ans[cnt++] = pair<int, int>(b, a);
  ans[cnt++] = pair<int, int>(a, b);
}
int work() {
  read(n);
  int p1 = 1, p2 = 1;
  for (int i = 1; i <= n; i++) {
    read(x[i]);
    if (a.insert(x[i], p1)) swp(i, p1), swap(x[i], x[p1++]);
  }
  for (int i = 1; i <= n; i++) {
    read(y[i]);
    if (!a.query(y[i])) {
      puts("-1");
      return 0;
    }
    if (b.insert(y[i], p2)) id[p2] = i, swap(y[i], y[p2++]);
  }
  for (int i = 1; i < p2; i++) {
    a = Linear_Basis();
    for (int j = 1; j < i; j++) a.insert(y[j], j);
    for (int j = i; j <= p1; j++) a.insert(x[j], j);
    vector<int> tmp;
    a.query(y[i], tmp);
    if (find(tmp.begin(), tmp.end(), i) == tmp.end())
      for (auto &j : tmp)
        if (j >= i) {
          swp(i, j), swap(x[i], x[j]);
          j = i;
          break;
        }
    for (auto j : tmp)
      if (j != i) ans[cnt++] = pair<int, int>(i, j);
  }
  for (int i = p2; i <= n; i++) {
    ans[cnt++] = pair<int, int>(i, i);
    vector<int> tmp;
    b.query(y[i], tmp);
    for (auto j : tmp) ans[cnt++] = pair<int, int>(i, j);
  }
  for (int i = p2 - 1; i > 0; i--)
    if (id[i]) swp(i, id[i]);
  write(cnt), putchar('\n');
  for (int i = 0; i < cnt; i++) printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }

### 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;
namespace zyt {
template <typename T>
inline bool read(T &x) {
  char c;
  bool f = false;
  x = 0;
  do c = getchar();
  while (c != EOF && c != '-' && !isdigit(c));
  if (c == EOF) return false;
  if (c == '-') f = true, c = getchar();
  do x = x * 10 + c - '0', c = getchar();
  while (isdigit(c));
  if (f) x = -x;
  return true;
}
template <typename T>
inline void write(T x) {
  static char buf[20];
  char *pos = buf;
  if (x < 0) putchar('-'), x = -x;
  do *pos++ = x % 10 + '0';
  while (x /= 10);
  while (pos > buf) putchar(*--pos);
}
const int N = 1e4 + 10, M = 1e6 + 10, B = 31;
bool check(const int a, const int p) { return a & (1 << p); }
class Linear_Basis {
 private:
  int a[B], b[B], msk[B];

 public:
  Linear_Basis() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    memset(msk, 0, sizeof(msk));
  }
  bool insert(int x, const int id) {
    int m = 0;
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i], m ^= msk[i];
        else {
          a[i] = x, b[i] = id, msk[i] = (m ^ (1 << i));
          return true;
        }
      }
    return false;
  }
  bool query(int x) const {
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i];
        else
          return false;
      }
    return true;
  }
  bool query(int x, vector<int> &v) const {
    v.clear();
    int m = 0;
    for (int i = B - 1; i >= 0; i--)
      if (check(x, i)) {
        if (b[i])
          x ^= a[i], m ^= msk[i];
        else
          return false;
      }
    for (int i = 0; i < B; i++)
      if (check(m, i)) v.push_back(b[i]);
    return true;
  }
};
int n, x[N], y[N], cnt, id[N];
pair<int, int> ans[M];
Linear_Basis a, b;
void swp(const int a, const int b) {
  if (a == b) return;
  ans[cnt++] = pair<int, int>(a, b);
  ans[cnt++] = pair<int, int>(b, a);
  ans[cnt++] = pair<int, int>(a, b);
}
int work() {
  read(n);
  int p1 = 1, p2 = 1;
  for (int i = 1; i <= n; i++) {
    read(x[i]);
    if (a.insert(x[i], p1)) swp(i, p1), swap(x[i], x[p1++]);
  }
  for (int i = 1; i <= n; i++) {
    read(y[i]);
    if (!a.query(y[i])) {
      puts("-1");
      return 0;
    }
    if (b.insert(y[i], p2)) id[p2] = i, swap(y[i], y[p2++]);
  }
  for (int i = 1; i < p2; i++) {
    a = Linear_Basis();
    for (int j = 1; j < i; j++) a.insert(y[j], j);
    for (int j = i; j <= p1; j++) a.insert(x[j], j);
    vector<int> tmp;
    a.query(y[i], tmp);
    if (find(tmp.begin(), tmp.end(), i) == tmp.end())
      for (auto &j : tmp)
        if (j >= i) {
          swp(i, j), swap(x[i], x[j]);
          j = i;
          break;
        }
    for (auto j : tmp)
      if (j != i) ans[cnt++] = pair<int, int>(i, j);
  }
  for (int i = p2; i <= n; i++) {
    ans[cnt++] = pair<int, int>(i, i);
    vector<int> tmp;
    b.query(y[i], tmp);
    for (auto j : tmp) ans[cnt++] = pair<int, int>(i, j);
  }
  for (int i = p2 - 1; i > 0; i--)
    if (id[i]) swp(i, id[i]);
  write(cnt), putchar('\n');
  for (int i = 0; i < cnt; i++) printf("%d %d\n", ans[i].first, ans[i].second);
  return 0;
}
}  // namespace zyt
int main() { return zyt::work(); }

```