612_E. Square Root of Permutation_36765
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 java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.HashMap;
import java.util.Set;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
import java.util.LinkedList;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Andrey Rechitsky (arechitsky@gmail.com)
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		FastPrinter out = new FastPrinter(outputStream);
		TaskE solver = new TaskE();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskE {
    public void solve(int testNumber, FastScanner in, FastPrinter out) {
        int n = in.nextInt();
        int []p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = in.nextInt()-1;
        }
        HashMap<Integer, LinkedList<Integer>> cycles = new HashMap<Integer, LinkedList<Integer>>();
        boolean []vis = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (vis[i])continue;
            int size = 0;
            int cur = i;
            while (!vis[cur]){
                vis[cur] = true;
                size++;
                cur = p[cur];
            }
            LinkedList<Integer> l = cycles.get(size);
            if (l==null) {
                l = new LinkedList<Integer>();
                cycles.put(size, l);
            }
            l.add(i);
        }
        int [] ans = new int[n];
        for (int size: cycles.keySet()){
            LinkedList<Integer> l = cycles.get(size);
            if (size%2==0){
                if (l.size()%2==1){
                    out.printLine(-1);
                    return;
                }
                while (l.size()>0){
                    int c1 = l.poll();
                    int c2 = l.poll();
                    for (int i = 0; i < size; i++) {
                        ans[c1] = c2;
                        c1 = p[c1];
                        ans[c2] = c1;
                        c2 = p[c2];
                    }
                }
            }
            else {
                int d = size/2+1;
                while (l.size()>0){
                    int c1 = l.poll();
                    int c2 = c1;
                    for (int i = 0; i < d; i++) {
                        c2 = p[c2];
                    }
                    for (int i = 0; i < size; i++) {
                        ans[c1] = c2;
                        c1 = p[c1];
                        c2 = p[c2];
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) {
            out.print(ans[i]+1);
            out.print(' ');
        }
        out.printLine();
    }
}

class FastScanner {

    private BufferedReader reader;
    private StringTokenizer st;

    public FastScanner(InputStream stream) {
        this.reader = new BufferedReader(new InputStreamReader(stream));
        this.st = new StringTokenizer("");
    }

    public int nextInt() {
        return Integer.parseInt(next());
    }

    public String next() {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(readLine());
        }
        return st.nextToken();
    }

    private String readLine() {
        String line = tryReadLine();
        if (line == null) throw new InputMismatchException();
        return line;
    }

    private String tryReadLine() {
        try {
            return reader.readLine();
        } catch (IOException e) {
            throw new InputMismatchException();
        }
    }

}

class FastPrinter {
    private final PrintWriter writer;

    public FastPrinter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public void close() {
        writer.close();
    }

    public void printLine(long i) {
        writer.println(i);
    }

    public void printLine() {
        writer.println();
    }

    public void print(long i) {
        writer.print(i);
    }

    public void print(char c) {
        writer.print(c);
    }

}

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
