Educational Codeforces Round 4 |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

dfs and similar

graphs

math

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Square Root of Permutation

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputA 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* = *q*^{2} = [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 *q*^{2} = *p*. If there are several such *q* find any of them.

Input

The first line contains integer *n* (1 ≤ *n* ≤ 10^{6}) — the number of elements in permutation *p*.

The second line contains *n* distinct integers *p*_{1}, *p*_{2}, ..., *p*_{n} (1 ≤ *p*_{i} ≤ *n*) — the elements of permutation *p*.

Output

If there is no permutation *q* such that *q*^{2} = *p* print the number "-1".

If the answer exists print it. The only line should contain *n* different integers *q*_{i} (1 ≤ *q*_{i} ≤ *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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/08/2023 04:55:41 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|