Сізге ұзындығы $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_1 = d_1, c_2 = d_2, \dots, c_{i-1} = d_{i-1}$ және $c_i < d_i$ болатындай $i$ индексі табылса және тек сонда ғана $c$ тізбегі лексикографиялық тұрғыдан $d$ тізбегінен кіші болады.

Сіздің міндетіңіз — префикстік максимумдар тізбегі мүмкін болатын барлық $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