#include <bits/stdc++.h>
using namespace std;
void intarrayinput(int sz, int a[]) {
  for (int ___ = 0; ___ < sz; ++___) scanf("%d", a + ___);
}
void intarrayoutput(int sz, int a[]) {
  for (int ___ = 0; ___ < sz; ++___) printf("%d ", a[___]);
  printf("\n");
}
template <class T>
T emin(T& t1, T t2) {
  if (t1 > t2)
    return t1 = t2;
  else
    return t1;
}
template <class T>
T emax(T& t1, T t2) {
  if (t1 < t2)
    return t1 = t2;
  else
    return t1;
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> _p) {
  out << _p.first << " " << _p.second;
  return out;
}
template <class T>
ostream& operator<<(ostream& out, vector<T> _v) {
  for (int i = 0; i < _v.size(); ++i)
    out << _v[i] << (i + 1 == _v.size() ? "" : " ");
  return out;
}
template <class T>
void byebye(T t) {
  cout << t << endl;
  exit(0);
}
int n;
int p[1000005], ans[1000005];
int stk[1000005], tp;
vector<vector<int> > even_circle[1000005];
vector<vector<int> > odd_circle[1000005];
bool vis[1000005];
void dfs(int x) {
  if (vis[x]) {
    vector<int> now;
    now.clear();
    for (; tp; tp--) now.push_back(stk[tp - 1]);
    reverse(now.begin(), now.end());
    if (now.size() % 2 == 0)
      even_circle[now.size()].push_back(now);
    else
      odd_circle[now.size()].push_back(now);
    return;
  }
  stk[tp++] = x;
  vis[x] = true;
  dfs(p[x]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", p + i);
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    dfs(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (!odd_circle[i].size()) continue;
    for (vector<int> now : odd_circle[i]) {
      int len = now.size();
      int half = len / 2;
      ans[now[half]] = now[0];
      for (int j = half + 1; j < now.size(); ++j) {
        ans[now[j - half - 1]] = now[j];
        ans[now[j]] = now[j - half];
      }
      ans[now[(int)now.size() - 1]] = now[half];
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (even_circle[i].size() == 0) continue;
    if (even_circle[i].size() % 2) {
      puts("-1");
      return 0;
    }
    for (int j = 0; j < even_circle[i].size(); j += 2) {
      vector<int>& v1 = even_circle[i][j];
      vector<int>& v2 = even_circle[i][j + 1];
      for (int k = 0; k < v1.size(); ++k) {
        ans[v1[k]] = v2[k];
        if (k + 1 < v1.size()) ans[v2[k]] = v1[k + 1];
      }
      ans[v2[(int)v2.size() - 1]] = v1[0];
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d%c", ans[i], (i == n ? '\n' : ' '));
  }
  return 0;
}

### Prompt

Generate a Cpp solution 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;
void intarrayinput(int sz, int a[]) {
  for (int ___ = 0; ___ < sz; ++___) scanf("%d", a + ___);
}
void intarrayoutput(int sz, int a[]) {
  for (int ___ = 0; ___ < sz; ++___) printf("%d ", a[___]);
  printf("\n");
}
template <class T>
T emin(T& t1, T t2) {
  if (t1 > t2)
    return t1 = t2;
  else
    return t1;
}
template <class T>
T emax(T& t1, T t2) {
  if (t1 < t2)
    return t1 = t2;
  else
    return t1;
}
template <class T1, class T2>
ostream& operator<<(ostream& out, pair<T1, T2> _p) {
  out << _p.first << " " << _p.second;
  return out;
}
template <class T>
ostream& operator<<(ostream& out, vector<T> _v) {
  for (int i = 0; i < _v.size(); ++i)
    out << _v[i] << (i + 1 == _v.size() ? "" : " ");
  return out;
}
template <class T>
void byebye(T t) {
  cout << t << endl;
  exit(0);
}
int n;
int p[1000005], ans[1000005];
int stk[1000005], tp;
vector<vector<int> > even_circle[1000005];
vector<vector<int> > odd_circle[1000005];
bool vis[1000005];
void dfs(int x) {
  if (vis[x]) {
    vector<int> now;
    now.clear();
    for (; tp; tp--) now.push_back(stk[tp - 1]);
    reverse(now.begin(), now.end());
    if (now.size() % 2 == 0)
      even_circle[now.size()].push_back(now);
    else
      odd_circle[now.size()].push_back(now);
    return;
  }
  stk[tp++] = x;
  vis[x] = true;
  dfs(p[x]);
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", p + i);
  }
  memset(vis, 0, sizeof(vis));
  for (int i = 1; i <= n; ++i) {
    if (vis[i]) continue;
    dfs(i);
  }
  for (int i = 1; i <= n; ++i) {
    if (!odd_circle[i].size()) continue;
    for (vector<int> now : odd_circle[i]) {
      int len = now.size();
      int half = len / 2;
      ans[now[half]] = now[0];
      for (int j = half + 1; j < now.size(); ++j) {
        ans[now[j - half - 1]] = now[j];
        ans[now[j]] = now[j - half];
      }
      ans[now[(int)now.size() - 1]] = now[half];
    }
  }
  for (int i = 1; i <= n; ++i) {
    if (even_circle[i].size() == 0) continue;
    if (even_circle[i].size() % 2) {
      puts("-1");
      return 0;
    }
    for (int j = 0; j < even_circle[i].size(); j += 2) {
      vector<int>& v1 = even_circle[i][j];
      vector<int>& v2 = even_circle[i][j + 1];
      for (int k = 0; k < v1.size(); ++k) {
        ans[v1[k]] = v2[k];
        if (k + 1 < v1.size()) ans[v2[k]] = v1[k + 1];
      }
      ans[v2[(int)v2.size() - 1]] = v1[0];
    }
  }
  for (int i = 1; i <= n; ++i) {
    printf("%d%c", ans[i], (i == n ? '\n' : ' '));
  }
  return 0;
}

```