E. Корень квадратный из перестановки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка длины n — это такой массив длины n, который содержит каждое из чисел от 1 до n ровно по одному разу. Например, q = [4, 5, 1, 2, 3] — это перестановка. Для перестановки q ее квадратом называется такая перестановка p что p[i] = q[q[i]] для всех i = 1... n. Например, квадрат перестановки q = [4, 5, 1, 2, 3] равен p = q2 = [2, 3, 4, 5, 1].

Эта задача об обратном понятии — квадратном корне. Вам задана перестановка p ваша задача найти такую перестановку q, что q2 = p. Если искомых перестановок q несколько, найдите любую из них.

Входные данные

В первой строке находится целое число n (1 ≤ n ≤ 106) — количество элементов в перестановке p.

Во второй строке находятся n различных чисел pi (1 ≤ pi ≤ n) — элементы перестановки p.

Выходные данные

Если перестановки q такой, что q2 = p не существует, выведите число "-1".

Если же ответ существует, то нужно вывести его. Единственная строка должна содержать n различных чисел qi (1 ≤ qi ≤ n) — элементы перестановки q. Если существует несколько перестановок q, удовлетворяющих условию q·q = p, то разрешается вывести любую из них.

Примеры
Входные данные
4
2 1 4 3
Выходные данные
3 4 2 1
Входные данные
4
2 1 3 4
Выходные данные
-1
Входные данные
5
2 3 4 5 1
Выходные данные
4 5 1 2 3