Du får en følge av heltall med lengde $n$: $a_1, a_2, \dots, a_n$.

Betrakt alle $n$ mulige sykliske skift (rotasjoner) av denne følgen. For en startposisjon $p$ ($1 \le p \le n$) er det tilsvarende sykliske skiftet følgen

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

For denne skiftede følgen definerer vi dens prefiksmaksimumsfølge $c_1, c_2, \dots, c_n$ ved

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

Vi sammenligner to følger av samme lengde ved hjelp av vanlig leksikografisk ordning: $c$ er leksikografisk mindre enn $d$ hvis og bare hvis det finnes en indeks $i$ slik at $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ og $c_i < d_i$.

Din oppgave er å velge et syklisk skift av den opprinnelige følgen slik at prefiksmaksimumsfølgen blir leksikografisk minst blant alle $n$ mulige sykliske skift.

Inndata

Den første linjen inneholder et enkelt heltall $T$ ($1 \le T \le 2 \cdot 10^5$), antallet testtilfeller.

Hvert testtilfelle består av to linjer:

• Den første linjen inneholder et enkelt heltall $n$ ($1 \le n \le 5 \cdot 10^5$).
• Den andre linjen inneholder $n$ heltall $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Det er garantert at summen av $n$ over alle testtilfeller ikke overstiger $5 \cdot 10^5$.

Utdata

For hvert testtilfelle, skriv ut én linje som inneholder $n$ heltall: den leksikografisk minste prefiksmaksimumsfølgen etter syklisk skift.

Eksempel

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