Dany jest ciąg liczb całkowitych o długości $n$: $a_1, a_2, \dots, a_n$.

Rozważmy wszystkie $n$ możliwych przesunięć cyklicznych (rotacji) tego ciągu. Dla pozycji początkowej $p$ ($1 \le p \le n$) odpowiadającym jej przesunięciem cyklicznym jest ciąg

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

Dla tego przesuniętego ciągu definiujemy jego ciąg maksimów prefiksowych $c_1, c_2, \dots, c_n$ wzorem

$$c_i = \max(b_1, b_2, \dots, b_i) \quad \forall i = 1, 2, \dots, n.$$

Dwa ciągi tej samej długości porównujemy za pomocą zwykłego porządku leksykograficznego: ciąg $c$ jest mniejszy leksykograficznie od ciągu $d$ wtedy i tylko wtedy, gdy istnieje taki indeks $i$, że $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ oraz $c_i < d_i$.

Twoim zadaniem jest wybranie takiego przesunięcia cyklicznego pierwotnego ciągu, aby jego ciąg maksimów prefiksowych był najmniejszy leksykograficznie spośród wszystkich $n$ możliwych przesunięć cyklicznych.

Wejście

Pierwszy wiersz zawiera jedną liczbę całkowitą $T$ ($1 \le T \le 2 \cdot 10^5$), oznaczającą liczbę przypadków testowych.

Każdy przypadek testowy składa się z dwóch wierszy:

• Pierwszy wiersz zawiera jedną liczbę całkowitą $n$ ($1 \le n \le 5 \cdot 10^5$).
• Drugi wiersz zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Gwarantowane jest, że suma $n$ po wszystkich przypadkach testowych nie przekracza $5 \cdot 10^5$.

Wyjście

Dla każdego przypadku testowego wypisz jeden wiersz zawierający $n$ liczb całkowitych: najmniejszy leksykograficznie ciąg maksimów prefiksowych po przesunięciu cyklicznym.

Przykład

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