Terrain Route

Một nhà thám hiểm đang lên kế hoạch cho một tuyến đường gồm $n$ cột mốc liên tiếp từ trái sang phải. Nhà thám hiểm đã chọn trước $n$ giá trị cao độ cho các cột mốc và muốn sắp xếp thứ tự của chúng sao cho chênh lệch tuyệt đối giữa cao độ của cột mốc đầu tiên và cột mốc cuối cùng là nhỏ nhất có thể.

Bên cạnh đó, tuyến đường cần có độ thử thách cao. Do việc leo dốc hoặc di chuyển trên địa hình bằng phẳng tốn sức hơn xuống dốc, độ thử thách của tuyến đường được tính bằng số lượng chỉ số $i$ ($1 ≤ i < n$) thỏa mãn $h_i ≤ h_{i+1}$, trong đó $h_i$ là cao độ của cột mốc thứ $i$. Nhà thám hiểm muốn tận dụng toàn bộ các cột mốc đã khảo sát, do đó tất cả $n$ cột mốc đều phải được sử dụng trong tuyến đường.

Trong số tất cả các cách sắp xếp làm tối thiểu hóa $|h_1 - h_n|$, hãy tìm một cách sắp xếp có độ thử thách lớn nhất. Nếu có nhiều thứ tự cùng thỏa mãn các yêu cầu trên, bạn có thể đưa ra bất kỳ thứ tự nào hợp lệ.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên $t$ ($1 ≤ t ≤ 100$), biểu thị số lượng bộ thử nghiệm. Các bộ thử nghiệm được mô tả tiếp theo sau.

Dòng đầu tiên của mỗi bộ thử nghiệm chứa một số nguyên $n$ ($2 ≤ n ≤ 2 · 10^5$), biểu thị số lượng cột mốc; tổng của $n$ qua tất cả các bộ thử nghiệm không vượt quá $2 · 10^5$ ($\sum n ≤ 2 · 10^5$).

Dòng thứ hai của mỗi bộ thử nghiệm chứa $n$ số nguyên $h_1, h_2, ..., h_n$ ($1 ≤ h_i ≤ 10^9$), trong đó $h_i$ là cao độ của cột mốc thứ $i$.

Kết quả

Với mỗi bộ thử nghiệm, in ra $n$ số nguyên, biểu thị các cao độ đã cho theo một thứ tự tối đa hóa độ thử thách trong số tất cả các thứ tự tối thiểu hóa $|h_1 - h_n|$.

Nếu có nhiều thứ tự cùng thỏa mãn các yêu cầu trên, bạn có thể in ra bất kỳ thứ tự nào trong số đó.

Chấm điểm

Subtask 1 (30 points). $\sum n ≤ 2000$

Subtask 2 (70 points). $1 ≤ t ≤ 100$; $2 ≤ n ≤ 2 · 10^5$; $\sum n ≤ 2 · 10^5$

Ví dụ

Input

2
4
4 2 1 2
2
3 1

Output

2 4 1 2
1 3

Ghi chú

Trong bộ thử nghiệm đầu tiên của ví dụ:

Nhà thám hiểm bắt đầu tại cột mốc có cao độ $2$, tiếp theo đi lên cột mốc có cao độ $4$, làm độ thử thách tăng thêm $1$. Sau đó, người này đi xuống cột mốc có cao độ $1$, độ thử thách không đổi do đây là đoạn xuống dốc. Cuối cùng, nhà thám hiểm đi lên cột mốc có cao độ $2$, làm độ thử thách tăng thêm $1$. Chênh lệch tuyệt đối giữa cao độ ban đầu và cao độ kết thúc bằng $|2 - 2| = 0$, đây là giá trị nhỏ nhất có thể. Độ thử thách đạt giá trị lớn nhất bằng $2$.

Trong bộ thử nghiệm thứ hai của ví dụ:

Nhà thám hiểm bắt đầu tại cột mốc có cao độ $1$, tiếp theo đi lên cột mốc có cao độ $3$, làm độ thử thách tăng thêm $1$. Chênh lệch tuyệt đối giữa cao độ ban đầu và cao độ kết thúc bằng $|1 - 3| = 2$, đây là giá trị nhỏ nhất có thể vì tuyến đường chỉ gồm đúng hai cột mốc này. Độ thử thách đạt giá trị lớn nhất bằng $1$.