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 Solution {
 public:
  static const int MAXN = int(1e6) + 10;
  int n;
  int* by_ind;
  int* by_val;
  int* ans;
  vector<pair<int, int> > chains;
  bool* is_free;
  Solution() {
    by_ind = new int[MAXN]();
    by_val = new int[MAXN]();
    is_free = new bool[MAXN]();
    ans = new int[MAXN]();
  }
  void read_input(std::istream& in) {
    int cur;
    in >> n;
    for (int i = 1, lets_stop_here = (int)(n); i <= lets_stop_here; i++) {
      in >> cur;
      by_ind[i] = cur;
      by_val[cur] = i;
      is_free[cur] = true;
    }
  }
  bool has_answer(std::ostream& out) {
    bool has_answer = true;
    for (int i = 1, lets_stop_here = (int)(n); i <= lets_stop_here; i++) {
      has_answer = has_answer && ans[i] != 0;
    }
    return has_answer;
  }
  void print_answer(std::ostream& out) {
    if (has_answer(out)) {
      out << ans[1];
      for (int i = 2, lets_stop_here = (int)(n); i <= lets_stop_here; i++) {
        out << " " << ans[i];
      }
      out << ("\n");
    } else {
      out << -1 << ("\n");
    }
  }
  void mark_self() {
    for (int val = 1, lets_stop_here = (int)(n); val <= lets_stop_here; val++) {
      if (by_val[val] == val) {
        ans[val] = val;
        is_free[val] = false;
      }
    }
  }
  static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
    return a.second < b.second;
  }
  void handle_bendable_chain(int value, int chain_len) {
    vector<pair<int, int> > values;
    bool is_first = true;
    pair<int, int> c = make_pair(value, 0);
    while (is_first || c.first != value) {
      values.push_back(c);
      c = make_pair(by_val[c.first], (c.second + 2) % chain_len);
      is_first = false;
    }
    sort(values.begin(), values.end(), cmp);
    int prev_ind = 0, cur_value;
    for (int i = 0, lets_stop_here = (int)(chain_len + 1); i < lets_stop_here;
         i++) {
      c = values[i % chain_len];
      cur_value = c.first;
      if (prev_ind > 0) {
        ans[prev_ind] = cur_value;
      }
      prev_ind = by_val[cur_value];
    }
  }
  void pair_two_chains(int v1, int v2) {
    int is_start, behind, behind_ind, ahead;
    is_start = true;
    behind = v1;
    ahead = v2;
    while (is_start || behind != v1) {
      behind_ind = by_val[behind];
      ans[behind_ind] = ahead;
      swap(behind, ahead);
      ahead = behind_ind;
      is_start = false;
    }
  }
  void handle_chains(std::ostream& out) {
    int start, cur, len;
    for (int val = 1, lets_stop_here = (int)(n); val <= lets_stop_here; val++) {
      start = val;
      cur = start;
      len = 0;
      while (is_free[cur]) {
        is_free[cur] = false;
        len += 1;
        cur = by_val[cur];
      }
      if (len > 0) {
        chains.push_back(make_pair(start, len));
      }
    }
    int prev_val = 0, prev_chain_len = 0;
    int val, chain_len, chains_len = chains.size();
    pair<int, int> c;
    sort(chains.begin(), chains.end(), cmp);
    for (int i = 0, lets_stop_here = (int)(chains_len); i < lets_stop_here;
         i++) {
      c = chains[i];
      val = c.first;
      chain_len = c.second;
      if (chain_len % 2 == 1) {
        handle_bendable_chain(val, chain_len);
      } else {
        if (prev_val == 0) {
          prev_val = val;
          prev_chain_len = chain_len;
        } else if (prev_chain_len == chain_len) {
          pair_two_chains(prev_val, val);
          prev_val = 0;
        } else {
          break;
        }
      }
    }
  }
  void solve(std::istream& in, std::ostream& out) {
    read_input(in);
    mark_self();
    handle_chains(out);
    print_answer(out);
  }
};
void solve(std::istream& in, std::ostream& out) {
  out << std::setprecision(12);
  Solution solution;
  solution.solve(in, out);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  istream& in = cin;
  ostream& out = cout;
  solve(in, out);
  return 0;
}
