Sắp xếp hiệu liền kề

Cho một mảng gồm $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Hãy sắp xếp lại các số này sao cho thỏa mãn:

$$|a_1-a_2|\le |a_2-a_3|\le \dots \le |a_{n-1}-a_n|,$$

trong đó $|x|$ là giá trị tuyệt đối của $x$.

Nói cách khác, các giá trị tuyệt đối của hiệu hai phần tử liên tiếp phải không giảm dọc theo dãy. Luôn tồn tại ít nhất một cách sắp xếp thỏa mãn. Lưu ý các số trong mảng không nhất thiết phân biệt — một số giá trị có thể trùng nhau.

Bạn phải trả lời $t$ bộ dữ liệu độc lập.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ — số lượng bộ dữ liệu.
• Với mỗi bộ dữ liệu:
  • Dòng đầu chứa số nguyên $n$ — độ dài mảng.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một hoán vị của mảng $a$ thỏa mãn điều kiện đã cho. Nếu có nhiều đáp án hợp lệ, in ra bất kỳ đáp án nào.

Ràng buộc

• $1\le t\le {10}^4$
• $3\le n\le {10}^5$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^5$.
• $-{10}^9\le a_i\le {10}^9$

Ví dụ