#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
vector<int> p;
vector<vector<int> > oddCycles, evenCycles;
void cntCycles() {
  int n = int(p.size());
  vector<bool> vis(n);
  oddCycles.clear(), evenCycles.clear();
  for (int i = 0; i < n; i++) {
    int cur = p[i];
    vector<int> cycle;
    while (!vis[cur]) {
      vis[cur] = true;
      cycle.push_back(cur);
      cur = p[cur];
    }
    if (!cycle.empty()) {
      if (int(cycle.size()) % 2 == 1)
        oddCycles.push_back(cycle);
      else
        evenCycles.push_back(cycle);
    }
  }
  return;
}
vector<int> convertCyclesToPerm(vector<vector<int> > cycles) {
  vector<int> q(int(p.size()));
  for (auto cycle : cycles) {
    int sz = cycle.size();
    for (int i = 0; i < sz; i++) {
      int cur = cycle[i], nxt = cycle[(i + 1) % sz];
      q[cur] = nxt;
    }
  }
  return q;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  int n;
  cin >> n;
  p.resize(n);
  for (auto &i : p) cin >> i;
  for (auto &i : p) --i;
  vector<vector<int> > cycles;
  vector<int> lengthCnt(n + 1);
  cntCycles();
  for (auto cycle : evenCycles) lengthCnt[int(cycle.size())]++;
  bool ok = true;
  for (int i = 0; i <= n; i += 2) {
    if (lengthCnt[i] % 2 == 1) {
      ok = false;
      break;
    }
  }
  if (!ok) {
    cout << -1 << '\n';
    return 0;
  }
  vector<vector<int> > newCycles;
  for (auto cycle : oddCycles) {
    vector<int> new_cycle;
    int lf = 0, rg = (int(cycle.size()) + 1) / 2;
    int cnt = 0;
    while (cnt < int(cycle.size())) {
      new_cycle.push_back(cycle[lf]);
      ++cnt;
      if (cnt < int(cycle.size())) new_cycle.push_back(cycle[rg]);
      ++cnt;
      ++lf, ++rg;
    }
    newCycles.push_back(new_cycle);
  }
  sort(evenCycles.begin(), evenCycles.end(), [](vector<int> x, vector<int> y) {
    if (x.size() == y.size()) return x[0] < y[0];
    return int(x.size()) < int(y.size());
  });
  for (int i = 1; i < int(evenCycles.size()); i += 2) {
    vector<int> cycle1 = evenCycles[i], cycle2 = evenCycles[i - 1];
    assert(int(cycle1.size()) == int(cycle2.size()));
    vector<int> new_cycle;
    for (int i = 0; i < cycle1.size(); i++) {
      new_cycle.push_back(cycle1[i]);
      new_cycle.push_back(cycle2[i]);
    }
    newCycles.push_back(new_cycle);
  }
  vector<int> q = convertCyclesToPerm(newCycles);
  for (auto i : q) cout << i + 1 << " ";
  cout << '\n';
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const int MOD = 1e9 + 7;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << '\n'; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
vector<int> p;
vector<vector<int> > oddCycles, evenCycles;
void cntCycles() {
  int n = int(p.size());
  vector<bool> vis(n);
  oddCycles.clear(), evenCycles.clear();
  for (int i = 0; i < n; i++) {
    int cur = p[i];
    vector<int> cycle;
    while (!vis[cur]) {
      vis[cur] = true;
      cycle.push_back(cur);
      cur = p[cur];
    }
    if (!cycle.empty()) {
      if (int(cycle.size()) % 2 == 1)
        oddCycles.push_back(cycle);
      else
        evenCycles.push_back(cycle);
    }
  }
  return;
}
vector<int> convertCyclesToPerm(vector<vector<int> > cycles) {
  vector<int> q(int(p.size()));
  for (auto cycle : cycles) {
    int sz = cycle.size();
    for (int i = 0; i < sz; i++) {
      int cur = cycle[i], nxt = cycle[(i + 1) % sz];
      q[cur] = nxt;
    }
  }
  return q;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  ;
  int n;
  cin >> n;
  p.resize(n);
  for (auto &i : p) cin >> i;
  for (auto &i : p) --i;
  vector<vector<int> > cycles;
  vector<int> lengthCnt(n + 1);
  cntCycles();
  for (auto cycle : evenCycles) lengthCnt[int(cycle.size())]++;
  bool ok = true;
  for (int i = 0; i <= n; i += 2) {
    if (lengthCnt[i] % 2 == 1) {
      ok = false;
      break;
    }
  }
  if (!ok) {
    cout << -1 << '\n';
    return 0;
  }
  vector<vector<int> > newCycles;
  for (auto cycle : oddCycles) {
    vector<int> new_cycle;
    int lf = 0, rg = (int(cycle.size()) + 1) / 2;
    int cnt = 0;
    while (cnt < int(cycle.size())) {
      new_cycle.push_back(cycle[lf]);
      ++cnt;
      if (cnt < int(cycle.size())) new_cycle.push_back(cycle[rg]);
      ++cnt;
      ++lf, ++rg;
    }
    newCycles.push_back(new_cycle);
  }
  sort(evenCycles.begin(), evenCycles.end(), [](vector<int> x, vector<int> y) {
    if (x.size() == y.size()) return x[0] < y[0];
    return int(x.size()) < int(y.size());
  });
  for (int i = 1; i < int(evenCycles.size()); i += 2) {
    vector<int> cycle1 = evenCycles[i], cycle2 = evenCycles[i - 1];
    assert(int(cycle1.size()) == int(cycle2.size()));
    vector<int> new_cycle;
    for (int i = 0; i < cycle1.size(); i++) {
      new_cycle.push_back(cycle1[i]);
      new_cycle.push_back(cycle2[i]);
    }
    newCycles.push_back(new_cycle);
  }
  vector<int> q = convertCyclesToPerm(newCycles);
  for (auto i : q) cout << i + 1 << " ";
  cout << '\n';
  return 0;
}

```