נתונה לך סדרה של מספרים שלמים באורך $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