No tag edit access

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-2017 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/23/2017 09:17:20 (c4).

Desktop version, switch to mobile version.

User lists

Name |
---|