oolimry 有一个长度为 $$$n$$$ 的数组 $$$a$$$,他非常喜欢。今天,你把他的数组改为$$$b$$$,$$$a$$$的排列,让他伤心。
因为oolimry只是一只鸭子,所以他只能执行以下操作来恢复他的阵列:
- 选择两个整数 $$$i,j$$$ 使得 $$$1 \leq i,j \leq n$$$。
- 交换 $$$b_i$$$ 和 $$$b_j$$$。
数组 $$$b$$$ 的悲伤度是将 $$$b$$$ 转换为 $$$a$$$ 所需的最少操作数。
给定数组 $$$a$$$,找到任何数组 $$$b$$$,它是 $$$a$$$ 的排列,并且在数组 $$$a$$$ 的所有排列中具有最大悲伤度。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — 数组的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — 数组 $$$a$$$ 的元素。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ — 描述数组 $$$b$$$。如果有多个答案,您可以打印其中一个。
示例
输入 #1
2 2 2 1 4 1 2 3 3
输出 #1
1 2 3 3 2 1
注意
在第一个测试用例中,数组 $$$[1,2]$$$ 有悲伤 $$$1$$$。我们可以使用 $$$(i,j)=(1,2)$$$ 的一个操作将 $$$[1,2]$$$ 转换为 $$$[2,1]$$$。
在第二个测试用例中,数组 $$$[3,3,2,1]$$$ 有悲伤 $$$2$$$。我们可以通过 $$$(i,j)=(1,4)$$$ 和 $$$(i,j)=(2,3)$$$ 两个操作将 $$$[3,3,2,1]$$$ 转换为 $$$[1,2,3,3]$$$ 。