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
#include <bits/stdc++.h>
using namespace std;
class permutation {
  int sz;
  int *p;
  vector<vector<int>> permtocycle() const {
    vector<vector<int>> cycle;
    vector<bool> used(sz, 0);
    for (int i = 0; i < sz; ++i) {
      if (!used[i]) {
        vector<int> cyc;
        int idx = i;
        while (true) {
          cyc.push_back(idx);
          used[idx] = true;
          idx = p[idx];
          if (idx == i) break;
        }
        int maxpos, ma = -1;
        for (int i = 0; i < cyc.size(); ++i) {
          if (ma < cyc[i]) {
            ma = cyc[i];
            maxpos = i;
          }
        }
        rotate(cyc.begin(), cyc.begin() + maxpos, cyc.end());
        cycle.push_back(cyc);
      }
    }
    return cycle;
  }

 public:
  permutation(int n, int a[]) {
    sz = n;
    p = new int[sz];
    for (int i = 0; i < sz; ++i) {
      p[i] = a[i];
    }
  }
  permutation(const permutation &q) {
    sz = q.sz;
    p = new int[sz];
    for (int i = 0; i < sz; ++i) {
      p[i] = q.p[i];
    }
  }
  permutation operator=(const permutation &q) {
    if (this != &q) {
      delete[] p;
      sz = q.sz;
      p = new int[sz];
      for (int i = 0; i < sz; ++i) {
        p[i] = q.p[i];
      }
    }
    return *this;
  }
  permutation operator-() const {
    int *invp;
    invp = new int[sz];
    for (int i = 0; i < sz; ++i) {
      invp[p[i]] = i;
    }
    permutation res(sz, invp);
    return res;
  }
  permutation operator*(permutation const &q) const {
    int *pr;
    pr = new int[sz];
    for (int i = 0; i < sz; ++i) {
      pr[i] = p[q.p[i]];
    }
    permutation res(sz, pr);
    return res;
  }
  int size() const { return sz; }
  int *to_array() const { return p; }
  permutation const operator^(long long i) const {
    if (i == 0) {
      int identity[sz];
      for (int j = 0; j < sz; ++j) {
        identity[j] = j;
      }
      permutation res(sz, identity);
      return res;
    }
    if (i % 2 == 1) {
      return (*this) * ((*this) ^ (i - 1));
    }
    return ((*this) * (*this)) ^ (i / 2);
  }
  permutation const square_root(int &flag) {
    vector<vector<int>> v = permtocycle();
    sort(v.begin(), v.end(), [](const vector<int> &v1, const vector<int> &v2) {
      return v1.size() < v2.size();
    });
    int ans[sz];
    for (int i = 0; i < v.size();) {
      int len = v[i].size();
      if (len & 1) {
        if (len == 1) {
          ans[v[i][0]] = v[i][0];
          ++i;
          continue;
        }
        int idx = 0;
        while (idx != (v[i].size() - 1) / 2) {
          if (idx < (v[i].size() + 1) / 2) {
            ans[v[i][idx]] = v[i][idx + (v[i].size() + 1) / 2];
            idx += (v[i].size() + 1) / 2;
          } else {
            ans[v[i][idx]] = v[i][idx - (v[i].size() - 1) / 2];
            idx -= (v[i].size() - 1) / 2;
          }
        }
        ans[v[i][idx]] = v[i][0];
        i++;
      } else {
        if (i + 1 < v.size() && v[i + 1].size() == v[i].size()) {
          int idx = 0, ok = 0;
          while (!(ok == 1 && idx == len - 1)) {
            if (ok == 0) {
              ans[v[i][idx]] = v[i + 1][idx];
              ok = 1;
            } else {
              ans[v[i + 1][idx]] = v[i][idx + 1];
              idx++;
              ok = 0;
            }
          }
          ans[v[i + 1][idx]] = v[i][0];
          i += 2;
        } else {
          flag = 0;
          int identity[sz];
          iota(identity, identity + sz, 0);
          return permutation(sz, identity);
        }
      }
    }
    return permutation(sz, ans);
  }
};
int main() {
  int n;
  cin >> n;
  int a[n];
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    a[i]--;
  }
  permutation p(n, a);
  int f = 1;
  permutation q = p.square_root(f);
  if (f == 0)
    cout << "-1\n";
  else {
    for (int i = 0; i < q.size(); i++) {
      cout << q.to_array()[i] + 1 << " ";
    }
    cout << "\n";
  }
  return 0;
}
