給定一個包含 $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 \forall i = 1, 2, \dots, n.$$

我們使用通常的字典序來比較兩個相同長度的序列：$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$ 個整數：循環移位後字典序最小的前綴最大值序列。

範例

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 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