Вам задано послідовність цілих чисел довжини $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