Ti viene data una sequenza di interi di lunghezza $n$: $a_1, a_2, \dots, a_n$.

Considera tutti gli $n$ possibili scorrimenti ciclici (rotazioni) di questa sequenza. Per una posizione iniziale $p$ ($1 \le p \le n$), lo scorrimento ciclico corrispondente è la sequenza

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

Per questa sequenza traslata, definisci la sua sequenza dei massimi dei prefissi $c_1, c_2, \dots, c_n$ come

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

Confrontiamo due sequenze della stessa lunghezza usando l'usuale ordine lessicografico: $c$ è lessicograficamente minore di $d$ se e solo se esiste un indice $i$ tale che $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ e $c_i < d_i$.

Il tuo compito è scegliere uno scorrimento ciclico della sequenza originale in modo tale che la sua sequenza dei massimi dei prefissi sia lessicograficamente minima tra tutti gli $n$ possibili scorrimenti ciclici.

Input

La prima riga contiene un singolo intero $T$ ($1 \le T \le 2 \cdot 10^5$), il numero di casi di test.

Ciascun caso di test è composto da due righe:

• La prima riga contiene un singolo intero $n$ ($1 \le n \le 5 \cdot 10^5$).
• La seconda riga contiene $n$ interi $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

È garantito che la somma di $n$ su tutti i casi di test non superi $5 \cdot 10^5$.

Output

Per ciascun caso di test, stampa una riga contenente $n$ interi: la sequenza dei massimi dei prefissi lessicograficamente minima dopo uno scorrimento ciclico.

Esempio

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