612_E. Square Root of Permutation_36762
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
from __future__ import division
from collections import defaultdict
import random
#import numpy as np

def get_cycle(perm, i):
    start = i
    current = i
    res = [i]
    while True:
        new = perm[current]
        perm[current] = -1
        current = new
        if current == start:
            return res
        res.append(current)

def invert_odd_cycle(res, cycle):
    n = len(cycle)
    m = (n - 1) // 2
    for i, e in enumerate(cycle):
        res[e] = cycle[(n + i - m) % n]

def invert_two_even_cycles(res, cycle1, cycle2):
    n = len(cycle1)
    for i in range(n):
        res[cycle1[i]] = cycle2[i]
        res[cycle2[i]] = cycle1[(i+1)%n]

def _sqrtp(perm):
    perm = list(perm)
    res = [None] * len(perm)
    start = 0
    even_cycles = defaultdict(list)
    while True:
        while perm[start] == -1:
            start += 1
            if start >= len(perm):
                for cycles in even_cycles.values():
                    if len(cycles) % 2 == 1:
                        return -1
                    for i in range(len(cycles) // 2):
                        invert_two_even_cycles(res, cycles[2 * i], cycles[2 * i + 1])
                return tuple(res)

        cycle = get_cycle(perm, start)
        if len(cycle) % 2 == 1:
            invert_odd_cycle(res, cycle)
        else:
            even_cycles[len(cycle)].append(cycle)


def sqrtp(perm):
    res = _sqrtp(decp(perm))
    if isinstance(res, tuple):
        return incp(res)
    else:
        return res

def _sqrp(perm):
    res = [None]*len(perm)
    for i,e in enumerate(perm):
        res[i] = perm[perm[i]]
    return tuple(res)

def sqrp(perm):
    return incp(_sqrp(decp(perm)))

def incp(perm):
    return tuple(n + 1 for n in perm)

def decp(perm):
    return tuple(n - 1 for n in perm)

def randp(n):
    res = list(range(n))
    for i in range(1, n):
        #j = np.random.randint(0, i)
        j = random.randint(0, i)
        a = res[i]
        res[i] = res[j]
        res[j] = a
    return incp(res)

raw_input()
perm = map(int, raw_input().split())
res = sqrtp(perm)
print(' '.join(map(str, res)) if isinstance(res, tuple) else res)

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
