#include <bits/stdc++.h>
using namespace std;
template <class A>
void rd(vector<A>& v);
template <class T>
void rd(T& x) {
  cin >> x;
}
template <class H, class... T>
void rd(H& h, T&... t) {
  rd(h);
  rd(t...);
}
template <class A>
void rd(vector<A>& x) {
  for (auto& a : x) rd(a);
}
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
void __p(T a) {
  cout << a;
}
template <typename T, typename F>
void __p(pair<T, F> a) {
  cout << "{";
  __p(a.first);
  cout << ",";
  __p(a.second);
  cout << "}\n";
}
template <typename T>
void __p(std::vector<T> a) {
  cout << "{";
  for (auto it = a.begin(); it < a.end(); it++)
    __p(*it), cout << ",}\n"[it + 1 == a.end()];
}
template <typename T, typename... Arg>
void __p(T a1, Arg... a) {
  __p(a1);
  __p(a...);
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : ";
  __p(arg1);
  cout << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  int64_t bracket = 0, i = 0;
  for (;; i++)
    if (names[i] == ',' && bracket == 0)
      break;
    else if (names[i] == '(')
      bracket++;
    else if (names[i] == ')')
      bracket--;
  const char* comma = names + i;
  cout.write(names, comma - names) << " : ";
  __p(arg1);
  cout << " | ";
  __f(comma + 1, args...);
}
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  if (((int64_t)(s).size())) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
signed main() {
  setIO();
  int64_t n;
  rd(n);
  vector<int64_t> p(n), nxt(n);
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    rd(p[i]);
    --p[i];
    nxt[i] = p[i];
  }
  vector<vector<int64_t>> cyc[n + 1], ans;
  vector<int64_t> vis(n, 0);
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    if (!vis[i]) {
      vector<int64_t> temp;
      while (!vis[i]) {
        temp.push_back(i);
        vis[i] = 1;
        i = nxt[i];
      }
      cyc[((int64_t)(temp).size())].push_back(temp);
    }
  }
  for (int64_t SZ = int64_t(1); SZ < int64_t(n + 1); ++SZ) {
    if (SZ % 2 == 0) {
      if (((int64_t)(cyc[SZ]).size()) % 2 == 1) {
        cout << -1;
        exit(0);
      }
      while (((int64_t)(cyc[SZ]).size())) {
        auto v1 = cyc[SZ].back();
        cyc[SZ].pop_back();
        auto v2 = cyc[SZ].back();
        cyc[SZ].pop_back();
        vector<int64_t> temp;
        reverse((v1).begin(), (v1).end());
        reverse((v2).begin(), (v2).end());
        for (int64_t i = int64_t(0); i < int64_t(2 * SZ); ++i) {
          if (i % 2 == 0) {
            temp.push_back(v1.back());
            v1.pop_back();
          } else {
            temp.push_back(v2.back());
            v2.pop_back();
          }
        }
        ans.push_back(temp);
      }
    } else {
      for (auto v : cyc[SZ]) {
        vector<int64_t> even, odd;
        for (int64_t i = int64_t(0); i < int64_t(SZ); ++i) {
          if (i % 2 == 0) {
            even.push_back(i);
          } else {
            odd.push_back(i);
          }
        }
        reverse((even).begin(), (even).end());
        reverse((odd).begin(), (odd).end());
        vector<int64_t> temp(SZ);
        for (auto i : v) {
          if (((int64_t)(even).size())) {
            temp[even.back()] = i;
            even.pop_back();
          } else {
            temp[odd.back()] = i;
            odd.pop_back();
          }
        }
        ans.push_back(temp);
      }
    }
  }
  vector<int64_t> output(n);
  for (auto v : ans) {
    for (int64_t i = int64_t(0); i < int64_t(((int64_t)(v).size())); ++i) {
      output[v[i]] = v[(i + 1) % ((int64_t)(v).size())];
    }
  }
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    cout << output[i] + 1 << ' ';
    assert(p[i] == output[output[i]]);
  }
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 <class A>
void rd(vector<A>& v);
template <class T>
void rd(T& x) {
  cin >> x;
}
template <class H, class... T>
void rd(H& h, T&... t) {
  rd(h);
  rd(t...);
}
template <class A>
void rd(vector<A>& x) {
  for (auto& a : x) rd(a);
}
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
void __p(T a) {
  cout << a;
}
template <typename T, typename F>
void __p(pair<T, F> a) {
  cout << "{";
  __p(a.first);
  cout << ",";
  __p(a.second);
  cout << "}\n";
}
template <typename T>
void __p(std::vector<T> a) {
  cout << "{";
  for (auto it = a.begin(); it < a.end(); it++)
    __p(*it), cout << ",}\n"[it + 1 == a.end()];
}
template <typename T, typename... Arg>
void __p(T a1, Arg... a) {
  __p(a1);
  __p(a...);
}
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : ";
  __p(arg1);
  cout << "\n";
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  int64_t bracket = 0, i = 0;
  for (;; i++)
    if (names[i] == ',' && bracket == 0)
      break;
    else if (names[i] == '(')
      bracket++;
    else if (names[i] == ')')
      bracket--;
  const char* comma = names + i;
  cout.write(names, comma - names) << " : ";
  __p(arg1);
  cout << " | ";
  __f(comma + 1, args...);
}
void setIO(string s = "") {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin.exceptions(cin.failbit);
  if (((int64_t)(s).size())) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
  }
}
signed main() {
  setIO();
  int64_t n;
  rd(n);
  vector<int64_t> p(n), nxt(n);
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    rd(p[i]);
    --p[i];
    nxt[i] = p[i];
  }
  vector<vector<int64_t>> cyc[n + 1], ans;
  vector<int64_t> vis(n, 0);
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    if (!vis[i]) {
      vector<int64_t> temp;
      while (!vis[i]) {
        temp.push_back(i);
        vis[i] = 1;
        i = nxt[i];
      }
      cyc[((int64_t)(temp).size())].push_back(temp);
    }
  }
  for (int64_t SZ = int64_t(1); SZ < int64_t(n + 1); ++SZ) {
    if (SZ % 2 == 0) {
      if (((int64_t)(cyc[SZ]).size()) % 2 == 1) {
        cout << -1;
        exit(0);
      }
      while (((int64_t)(cyc[SZ]).size())) {
        auto v1 = cyc[SZ].back();
        cyc[SZ].pop_back();
        auto v2 = cyc[SZ].back();
        cyc[SZ].pop_back();
        vector<int64_t> temp;
        reverse((v1).begin(), (v1).end());
        reverse((v2).begin(), (v2).end());
        for (int64_t i = int64_t(0); i < int64_t(2 * SZ); ++i) {
          if (i % 2 == 0) {
            temp.push_back(v1.back());
            v1.pop_back();
          } else {
            temp.push_back(v2.back());
            v2.pop_back();
          }
        }
        ans.push_back(temp);
      }
    } else {
      for (auto v : cyc[SZ]) {
        vector<int64_t> even, odd;
        for (int64_t i = int64_t(0); i < int64_t(SZ); ++i) {
          if (i % 2 == 0) {
            even.push_back(i);
          } else {
            odd.push_back(i);
          }
        }
        reverse((even).begin(), (even).end());
        reverse((odd).begin(), (odd).end());
        vector<int64_t> temp(SZ);
        for (auto i : v) {
          if (((int64_t)(even).size())) {
            temp[even.back()] = i;
            even.pop_back();
          } else {
            temp[odd.back()] = i;
            odd.pop_back();
          }
        }
        ans.push_back(temp);
      }
    }
  }
  vector<int64_t> output(n);
  for (auto v : ans) {
    for (int64_t i = int64_t(0); i < int64_t(((int64_t)(v).size())); ++i) {
      output[v[i]] = v[(i + 1) % ((int64_t)(v).size())];
    }
  }
  for (int64_t i = int64_t(0); i < int64_t(n); ++i) {
    cout << output[i] + 1 << ' ';
    assert(p[i] == output[output[i]]);
  }
}

```