Anda diberikan sebuah barisan bilangan bulat dengan panjang $n$: $a_1, a_2, \dots, a_n$.

Tinjau seluruh $n$ pergeseran siklik (rotasi) yang mungkin dari barisan ini. Untuk suatu posisi awal $p$ ($1 \le p \le n$), pergeseran siklik yang bersesuaian adalah barisan

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

Untuk barisan yang telah digeser ini, definisikan barisan maksimum prefiks-nya $c_1, c_2, \dots, c_n$ dengan

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

Kita membandingkan dua barisan dengan panjang yang sama menggunakan urutan leksikografis biasa: $c$ lebih kecil secara leksikografis daripada $d$ jika dan hanya jika terdapat suatu indeks $i$ sedemikian sehingga $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ dan $c_i < d_i$.

Tugas Anda adalah memilih suatu pergeseran siklik dari barisan asli sedemikian sehingga barisan maksimum prefiksnya paling kecil secara leksikografis di antara seluruh $n$ pergeseran siklik yang mungkin.

Masukan

Baris pertama berisi sebuah bilangan bulat tunggal $T$ ($1 \le T \le 2 \cdot 10^5$), yaitu banyaknya kasus uji.

Setiap kasus uji terdiri atas dua baris:

• Baris pertama berisi sebuah bilangan bulat tunggal $n$ ($1 \le n \le 5 \cdot 10^5$).
• Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Dijamin bahwa jumlah $n$ di seluruh kasus uji tidak melebihi $5 \cdot 10^5$.

Keluaran

Untuk setiap kasus uji, keluarkan satu baris yang berisi $n$ bilangan bulat: barisan maksimum prefiks yang paling kecil secara leksikografis setelah pergeseran siklik.

Contoh

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