تُعطى لك متتالية من الأعداد الصحيحة طولها $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