Вам дана последовательность целых чисел длины $n$: $a_1, a_2, \dots, a_n$.

Рассмотрим все $n$ возможных циклических сдвигов (вращений) этой последовательности. Для начальной позиции $p$ ($1 \le p \le n$) соответствующий циклический сдвиг представляет собой последовательность

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

Для этой сдвинутой последовательности определим её последовательность префиксных максимумов $c_1, c_2, \dots, c_n$ следующим образом:

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

Две последовательности одинаковой длины сравниваются в обычном лексикографическом порядке: $c$ лексикографически меньше $d$ тогда и только тогда, когда существует индекс $i$, такой что $c_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ и $c_i < d_i$.

Ваша задача — выбрать такой циклический сдвиг исходной последовательности, чтобы его последовательность префиксных максимумов была лексикографически наименьшей среди всех $n$ возможных циклических сдвигов.

Входные данные

Первая строка содержит одно целое число $T$ ($1 \le T \le 2 \cdot 10^5$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

• Первая строка содержит одно целое число $n$ ($1 \le n \le 5 \cdot 10^5$).
• Вторая строка содержит $n$ целых чисел $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$).

Гарантируется, что сумма $n$ по всем наборам входных данных не превосходит $5 \cdot 10^5$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую $n$ целых чисел: лексикографически наименьшую последовательность префиксных максимумов после циклического сдвига.

Пример

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