612_E. Square Root of Permutation_36764
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
import sys
#import random
from bisect import bisect_right as rb
from collections import deque
#sys.setrecursionlimit(10**8)
from queue import PriorityQueue
from math import *
input_ = lambda: sys.stdin.readline().strip("\r\n")
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab,bc,cd : ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x : print(x)
prinT = lambda x : print(x)
f = lambda : sys.stdout.flush()
mod = 10**9 + 7

n = ii()
a = [0] + il()

def dfs (i) :
    vis[i] = 1
    g.append(i)
    if (vis[a[i]] == 0) :
        dfs(a[i])

g = []
d = {}
vis = [0 for i in range (n+2)]

ans = [0 for i in range (n+1)]

for i in range (1,n+1) :
    if (vis[i] == 0) :
        i1 = i
        while True :
            vis[i1] = 1
            g.append(i1)

            if (vis[a[i1]] == 0) :
                i1 = a[i1]
            else :
                break

        l = len(g)

        if (l%2) :
            x = (l+1)//2

            for j in range (l) :
                ans[g[j]] = g[(x+j)%l]

        elif (d.get(l)) :
            v = d[l]

            for j in range (l) :
                ans[g[j]] = v[(j+1)%l]
                ans[v[j]] = g[j]

            del d[l]

        else :
            d[l] = g

        g = []

for i in d :
    print(-1)
    exit(0)

print(*ans[1:])



4
2 1 3 4
 4
2 1 4 3
 5
2 3 4 5 1
 10
3 5 1 2 10 8 7 6 4 9
 100
11 9 35 34 51 74 16 67 26 21 14 80 84 79 7 61 28 3 53 43 42 5 56 36 69 30 22 88 1 27 65 91 46 31 59 50 17 96 25 18 64 55 78 2 63 24 95 48 93 13 38 76 89 94 15 90 45 81 52 87 83 73 44 49 23 82 85 75 86 33 47 19 58 97 37 20 40 10 92 4 6 68 77 54 71 12 62 60 100 39 41 99 72 29 57 8 70 32 66 98
 1
1
 100
94 22 24 99 58 97 20 29 67 30 38 64 77 50 15 44 92 88 39 42 25 70 2 76 84 6 37 49 17 71 31 19 26 79 10 35 65 63 32 95 5 8 52 27 83 18 53 93 13 81 48 68 54 82 34 60 87 23 16 86 55 40 61 45 28 7 74 41 14 91 3 72 33 11 98 89 90 69 78 36 80 59 56 21 43 1 75 46 47 12 96 73 57 51 4 85 9 100 66 62
 10
8 2 10 3 4 6 1 7 9 5
 4
1 2 4 3
 4
1 4 2 3
 4
3 1 2 4
 10
8 3 10 2 4 6 1 7 9 5
 10
3 5 2 1 10 8 7 6 4 9
 5
1 3 4 5 2
 5
4 3 2 5 1

-1
 3 4 2 1  4 5 1 2 3
 6 9 8 10 4 3 7 1 5 2  -1
 1
 78 52 95 76 96 49 53 59 77 100 64 11 9 48 15 17 44 46 32 54 84 68 43 4 21 28 73 6 16 62 31 39 65 86 98 75 33 45 19 3 91 82 2 92 63 88 7 50 97 93 14 22 20 42 60 55 80 85 29 34 56 71 83 38 26 47 90 70 51 41 40 72 37 12 35 99 67 94 1 87 57 8 61 25 23 79 36 18 66 74 5 27 81 69 24 58 13 10 89 30
 -1
 -1
 1 3 4 2
 2 3 1 4
 7 5 4 10 3 6 8 1 9 2
 -1
 -1
 -1
