Дано перестановку (p_1, p_2, \ldots, p_n) цілих чисел від до . Знайдіть будь-яку перестановку (q_1, q_2, \ldots, q_n) цих чисел від до таку, що виконується наступна умова:
LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n})) є найбільшою серед усіх перестановок (q_1, q_2, \ldots, q_n).
Якщо існує декілька таких перестановок, знайдіть будь-яку з них.
Тут LCS(a, b) позначає довжину найбільшої спільної підпослідовності послідовностей і . Наприклад, LCS((1, 3, 4, 2, 5), (3, 1, 2, 4, 5)) = 3, а однією з спільних підпослідовностей довжини є (1, 2, 5).
Перший рядок містить одне ціле число (1 \le t \le 10^5) — кількість тестових наборів. Далі йде опис тестових наборів.
Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 10^6) — довжину перестановки.
Другий рядок кожного тестового набору містить цілих чисел p_1, p_2, \ldots, p_n (1 \le p_i \le n, всі p_i різні) — елементи перестановки.
Гарантується, що сума по всіх тестових наборах не перевищує 10^6.
Для кожного тестового набору виведіть цілих чисел q_1, q_2, \ldots, q_n (1 \le q_i \le n, всі q_i різні) — будь-яку перестановку цілих чисел від до , яка максимізує значення LCS((q_1, q_2, \ldots, q_n), (p_{q_1}, p_{q_2}, \ldots, p_{q_n})).
Приклад
У першому тестовому наборі, для q = (1, 2, 3, 4), маємо:
LCS((1, 2, 3, 4), (p_1, p_2, p_3, p_4)) = LCS((1, 2, 3, 4), (1, 2, 3, 4)) = 4.
У другому тестовому наборі, для q = (1, 6, 2, 5, 3, 4), маємо:
LCS((1, 6, 2, 5, 3, 4), (p_1, p_6, p_2, p_5, p_3, p_4)) = LCS((1, 6, 2, 5, 3, 4), (6, 1, 5, 2, 4, 3)) = 3; однією з спільних підпослідовностей довжиною є (1, 2, 3).