Se te da una secuencia de enteros de longitud $n$: $a_1, a_2, \dots, a_n$.

Considera los $n$ posibles desplazamientos cíclicos (rotaciones) de esta secuencia. Para una posición inicial $p$ ($1 \le p \le n$), el desplazamiento cíclico correspondiente es la secuencia

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

Para esta secuencia desplazada, define su secuencia de máximos de prefijos $c_1, c_2, \dots, c_n$ mediante

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

Comparamos dos secuencias de la misma longitud utilizando el orden lexicográfico habitual: $c$ es lexicográficamente menor que $d$ si y solo si existe un índice $i$ tal que $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ y $c_i < d_i$.

Tu tarea es elegir un desplazamiento cíclico de la secuencia original tal que su secuencia de máximos de prefijos sea lexicográficamente la más pequeña entre todos los $n$ desplazamientos cíclicos posibles.

Entrada

La primera línea contiene un solo entero $T$ ($1 \le T \le 2 \cdot 10^5$), el número de casos de prueba.

Cada caso de prueba consta de dos líneas:

• La primera línea contiene un solo entero $n$ ($1 \le n \le 5 \cdot 10^5$).
• La segunda línea contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Se garantiza que la suma de $n$ en todos los casos de prueba no supera $5 \cdot 10^5$.

Salida

Para cada caso de prueba, imprime una línea con $n$ enteros: la secuencia de máximos de prefijos lexicográficamente más pequeña después de un desplazamiento cíclico.

Ejemplo

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