Sinulle annetaan $n$ kokonaisluvun jono: $a_1, a_2, \dots, a_n$.

Tarkastellaan kaikkia tämän jonon $n$ mahdollista syklistä siirtoa (kiertoa). Aloituspaikalle $p$ ($1 \le p \le n$) vastaava syklinen siirto on jono

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

Määritellään tälle siirretylle jonolle sen alkuosien maksimijono $c_1, c_2, \dots, c_n$ kaavalla

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

Vertailemme kahta samanpituista jonoa tavanomaisessa aakkosjärjestyksessä (leksikografisessa järjestyksessä): $c$ on leksikografisesti pienempi kuin $d$ jos ja vain jos on olemassa sellainen indeksi $i$, että $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ ja $c_i < d_i$.

Tehtäväsi on valita alkuperäisen jonon syklinen siirto siten, että sen alkuosien maksimijono on leksikografisesti pienin kaikkien $n$ mahdollisen syklisen siirron joukossa.

Syöte

Ensimmäinen rivi sisältää yhden kokonaisluvun $T$ ($1 \le T \le 2 \cdot 10^5$), testitapausten lukumäärän.

Jokainen testitapaus koostuu kahdesta rivistä:

• Ensimmäinen rivi sisältää yhden kokonaisluvun $n$ ($1 \le n \le 5 \cdot 10^5$).
• Toinen rivi sisältää $n$ kokonaislukua $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

On taattu, että lukujen $n$ summa yli kaikkien testitapausten ei ylitä arvoa $5 \cdot 10^5$.

Tuloste

Tulosta jokaista testitapausta kohden yksi rivi, joka sisältää $n$ kokonaislukua: leksikografisesti pienin alkuosien maksimijono syklisen siirron jälkeen.

Esimerkki

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