#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
int gcdex(int a, int b, int &x, int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  int x1, y1;
  int g = gcdex(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return g;
}
inline int ADD_MOD(int a, int b) { return (a + b) % 1000000007; }
inline int MUL_MOD(int a, int b) { return (int64_t(a) * b) % 1000000007; }
inline int SUB_MOD(int a, int b) { return a >= b ? a - b : a + 1000000007 - b; }
int DIV_MOD(int a, int b) {
  int x, y;
  gcdex(b, 1000000007, x, y);
  int b1 = (x % 1000000007 + 1000000007) % 1000000007;
  return MUL_MOD(a, b1);
}
const long double EPS = 1. / 1e9;
inline bool EPS_EQUAL(long double a, long double b) {
  return abs(a - b) <= EPS;
}
inline bool EPS_LESS(long double a, long double b) { return b - a > EPS; }
inline bool EPS_GREATER(long double a, long double b) { return a - b > EPS; }
const int INF = 1e9;
const int64_t INF64 = 2e18;
void get_cycle(V<int> &a, V<uint8_t> &visited, int start, V<int> &c) {
  int i = start;
  while (a[i] != start) {
    c.push_back(a[i]);
    visited[a[i]] = 1;
    i = a[i];
  }
  c.push_back(start);
  visited[start] = 1;
}
void add_out_cycle(V<int> &b, V<int> &c) {
  for (int i = 0; i < c.size(); ++i) {
    int prev = i > 0 ? c[i - 1] : c.back();
    b[prev] = c[i];
  }
}
void add_odd_cycle(V<int> &b, V<int> &c) {
  int len = c.size();
  V<int> outC(len);
  for (int i = 0; i < len; ++i) {
    if (i % 2 == 0) {
      outC[i] = c[(len + i) / 2];
    } else {
      outC[i] = c[i / 2];
    }
  }
  add_out_cycle(b, outC);
}
void add_even_cycle(V<int> &b, V<int> &c1, V<int> &c2) {
  int len = c1.size();
  V<int> outC(len * 2);
  for (int i = 0; i < len; ++i) {
    outC[i * 2] = c1[i];
    outC[i * 2 + 1] = c2[i];
  }
  add_out_cycle(b, outC);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(15);
  int n;
  cin >> n;
  V<int> a(n);
  for (auto &i : a) {
    cin >> i;
    --i;
  }
  V<int> b(n);
  V<uint8_t> visited(n);
  V<V<int> > evenCycles(n + 1);
  int evenCyclesCount = 0;
  for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
      V<int> c;
      get_cycle(a, visited, i, c);
      int len = c.size();
      if (len % 2 == 1) {
        add_odd_cycle(b, c);
      } else {
        if (!evenCycles[len].empty()) {
          add_even_cycle(b, evenCycles[len], c);
          evenCycles[len].clear();
          evenCyclesCount--;
        } else {
          swap(evenCycles[len], c);
          evenCyclesCount++;
        }
      }
    }
  }
  if (evenCyclesCount > 0) {
    cout << -1 << endl;
    return 0;
  }
  for (auto &i : b) {
    cout << i + 1 << " ";
  }
  cout << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

A permutation of length n is an array containing each integer from 1 to n exactly once. For example, q = [4, 5, 1, 2, 3] is a permutation. For the permutation q the square of permutation is the permutation p that p[i] = q[q[i]] for each i = 1... n. For example, the square of q = [4, 5, 1, 2, 3] is p = q2 = [2, 3, 4, 5, 1].

This problem is about the inverse operation: given the permutation p you task is to find such permutation q that q2 = p. If there are several such q find any of them.

Input

The first line contains integer n (1 ≤ n ≤ 106) — the number of elements in permutation p.

The second line contains n distinct integers p1, p2, ..., pn (1 ≤ pi ≤ n) — the elements of permutation p.

Output

If there is no permutation q such that q2 = p print the number "-1".

If the answer exists print it. The only line should contain n different integers qi (1 ≤ qi ≤ n) — the elements of the permutation q. If there are several solutions print any of them.

Examples

Input

4
2 1 4 3


Output

3 4 2 1


Input

4
2 1 3 4


Output

-1


Input

5
2 3 4 5 1


Output

4 5 1 2 3

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
using V = vector<T>;
int gcdex(int a, int b, int &x, int &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  int x1, y1;
  int g = gcdex(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return g;
}
inline int ADD_MOD(int a, int b) { return (a + b) % 1000000007; }
inline int MUL_MOD(int a, int b) { return (int64_t(a) * b) % 1000000007; }
inline int SUB_MOD(int a, int b) { return a >= b ? a - b : a + 1000000007 - b; }
int DIV_MOD(int a, int b) {
  int x, y;
  gcdex(b, 1000000007, x, y);
  int b1 = (x % 1000000007 + 1000000007) % 1000000007;
  return MUL_MOD(a, b1);
}
const long double EPS = 1. / 1e9;
inline bool EPS_EQUAL(long double a, long double b) {
  return abs(a - b) <= EPS;
}
inline bool EPS_LESS(long double a, long double b) { return b - a > EPS; }
inline bool EPS_GREATER(long double a, long double b) { return a - b > EPS; }
const int INF = 1e9;
const int64_t INF64 = 2e18;
void get_cycle(V<int> &a, V<uint8_t> &visited, int start, V<int> &c) {
  int i = start;
  while (a[i] != start) {
    c.push_back(a[i]);
    visited[a[i]] = 1;
    i = a[i];
  }
  c.push_back(start);
  visited[start] = 1;
}
void add_out_cycle(V<int> &b, V<int> &c) {
  for (int i = 0; i < c.size(); ++i) {
    int prev = i > 0 ? c[i - 1] : c.back();
    b[prev] = c[i];
  }
}
void add_odd_cycle(V<int> &b, V<int> &c) {
  int len = c.size();
  V<int> outC(len);
  for (int i = 0; i < len; ++i) {
    if (i % 2 == 0) {
      outC[i] = c[(len + i) / 2];
    } else {
      outC[i] = c[i / 2];
    }
  }
  add_out_cycle(b, outC);
}
void add_even_cycle(V<int> &b, V<int> &c1, V<int> &c2) {
  int len = c1.size();
  V<int> outC(len * 2);
  for (int i = 0; i < len; ++i) {
    outC[i * 2] = c1[i];
    outC[i * 2 + 1] = c2[i];
  }
  add_out_cycle(b, outC);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.precision(15);
  int n;
  cin >> n;
  V<int> a(n);
  for (auto &i : a) {
    cin >> i;
    --i;
  }
  V<int> b(n);
  V<uint8_t> visited(n);
  V<V<int> > evenCycles(n + 1);
  int evenCyclesCount = 0;
  for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
      V<int> c;
      get_cycle(a, visited, i, c);
      int len = c.size();
      if (len % 2 == 1) {
        add_odd_cycle(b, c);
      } else {
        if (!evenCycles[len].empty()) {
          add_even_cycle(b, evenCycles[len], c);
          evenCycles[len].clear();
          evenCyclesCount--;
        } else {
          swap(evenCycles[len], c);
          evenCyclesCount++;
        }
      }
    }
  }
  if (evenCyclesCount > 0) {
    cout << -1 << endl;
    return 0;
  }
  for (auto &i : b) {
    cout << i + 1 << " ";
  }
  cout << endl;
  return 0;
}

```