给定一个包含 $n$ 个整数的序列：$a_1, a_2, \dots, a_n$。

考虑该序列所有 $n$ 种可能的循环移位（旋转）。对于起始位置 $p$（$1 \le p \le n$），对应的循环移位序列为

$$b_1, b_2, \dots, b_n = a_p, a_{p+1}, \dots, a_n, a_1, a_2, \dots, a_{p-1}$$

对于这个移位后的序列，定义其前缀最大值序列 $c_1, c_2, \dots, c_n$ 为

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \text{对于所有 } i = 1, 2, \dots, n\text{。}$$

我们使用通常的字典序来比较两个相同长度的序列：$c$ 的字典序小于 $d$ 当且仅当存在一个索引 $i$ 使得 $c_1 = d_1$，$c_2 = d_2$，$\dots$，$c_{i-1} = d_{i-1}$，并且 $c_i < d_i$。

你的任务是选择原序列的一个循环移位，使得其前缀最大值序列在所有 $n$ 种可能的循环移位中字典序最小。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^5$），表示测试用例的数量。对于每个测试用例：

第一行包含一个整数 $n$（$1 \le n \le 5 \cdot 10^5$）。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$）。

所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

输出格式

对于每个测试用例，输出一行包含 $n$ 个整数：循环移位后字典序最小的前缀最大值序列。

样例

输入 1

6
5
5 4 3 2 1
4
1 3 1 3
5
1 2 1 3 1
5
2 3 2 1 1
6
1 2 1 3 1 4
6
2 1 3 1 4 1

输出 1

1 5 5 5 5
1 3 3 3
1 1 2 2 3
1 1 2 3 3
1 2 2 3 3 4
1 2 2 3 3 4