คนแคระนักเดินทางตัดสินใจมุ่งความสนใจในปีนี้ไปที่การพิชิตยอดเขาต่างๆ ในเมืองวรอตสวัฟ เป้าหมายล่าสุดของเขาคือการพิชิตยอดเขาที่แตกต่างกัน $N$ ยอดภายในเวลา $N$ วันติดต่อกัน โดยพิชิตวันละหนึ่งยอดเขาพอดี การพิชิตยอดเขาเป็นเรื่องกล้วยๆ สำหรับนักเดินทาง เขาสามารถพิชิตยอดเขาใดก็ได้ในวันใดก็ได้ ด้วยเหตุนี้เขาจึงตัดสินใจทำให้การเดินทางสำรวจครั้งนี้ได้รับความสนใจจากสื่อให้มากที่สุดเท่าที่จะเป็นไปได้

เมื่อไม่นานมานี้ คนแคระได้สังเกตเห็นรูปแบบบางอย่าง:

• หลังจากพิชิตยอดเขาแรก ความสนใจของสื่อจะอยู่ในระดับสูง ไม่ว่ายอดเขานั้นจะมีความสูงเท่าใดก็ตาม
• หากในวันหนึ่งเขาพิชิตยอดเขาที่มีความสูง $a$ และในวันถัดไปพิชิตยอดเขาที่มีความสูง $b$ ความสนใจของสื่อต่อการสำรวจของเขาจะลดลง $\lfloor a/b \rfloor$ หน่วย ซึ่งเขาเรียกว่าหน่วยความสนใจของสื่อ

นักเดินทางทราบอยู่แล้วว่าเขาจะต้องพิชิตยอดเขา $N$ ยอดที่มีความสูง $a_1, \dots, a_N$ นอกจากนี้ยังปรากฏว่าความสูงของยอดเขาที่สูงที่สุดมีค่าไม่เกินสองเท่าของความสูงของยอดเขาที่ต่ำที่สุด คนแคระสามารถเลือกลำดับการพิชิตยอดเขาได้ตามต้องการ เป้าหมายของเขาคือการทำให้ผลรวมของการลดลงของหน่วยความสนใจของสื่อตลอดการเดินทางสำรวจทั้งหมดมีค่าน้อยที่สุด

คุณสามารถช่วยเขาเลือกลำดับการไปเยือนยอดเขาทั้งหมดเพื่อทำให้การลดลงของหน่วยความสนใจของสื่อมีค่าน้อยที่สุดได้หรือไม่?

ข้อมูลนำเข้า

บรรทัดแรกของข้อมูลนำเข้ามีจำนวน $T$ แทนจำนวนชุดข้อมูลทดสอบ

บรรทัดแรกของแต่ละชุดข้อมูลทดสอบมีจำนวนเต็ม $N$ เพียงจำนวนเดียว แทนจำนวนยอดเขาที่นักเดินทางจะต้องไปเยือน

บรรทัดที่สองของชุดข้อมูลทดสอบมีจำนวนเต็ม $N$ จำนวน คือ $a_1, \dots, a_N$ ซึ่งสอดคล้องกับเงื่อนไขที่ระบุไว้ในโจทย์

ข้อมูลส่งออก

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผลสองบรรทัด บรรทัดแรกประกอบด้วยจำนวนเต็มเพียงจำนวนเดียว แทนค่าการลดลงของหน่วยความสนใจของสื่อที่น้อยที่สุดที่เป็นไปได้สำหรับการเดินทางของคนแคระ

บรรทัดที่สองประกอบด้วยความสูง $a_1, \dots, a_N$ ที่เรียงตามลำดับที่คนแคระควรไปเยือนเพื่อให้ได้ค่าการลดลงที่น้อยที่สุดนี้

หากมีคำตอบที่เหมาะสมที่สุดหลายแบบ คุณสามารถแสดงผลแบบใดก็ได้

ขอบเขตข้อมูล

$1 \le T \le 100\,000, 1 \le N \le 10^6, 1 \le a_i \le 10^9, \max\{a_1, \dots, a_N\} \le 2 \cdot \min\{a_1, \dots, a_N\}$ และผลรวมของค่า $N$ ทั้งหมดที่ให้มาในข้อมูลนำเข้าไม่เกิน $10^6$

ตัวอย่าง

ข้อมูลนำเข้า 1

3
6
10 18 12 13 17 14
4
10 10 7 7
8
8 4 8 5 4 4 8 6

ข้อมูลส่งออก 1

0
10 12 13 14 17 18
1
7 10 7 10
4
4 4 4 5 6 8 8 8