Điện khí hóa

Cho $n$ điểm $a_1,a_2,\dots ,a_n$ nằm trên trục số. Với một số nguyên $k$ cho trước, hãy tìm một điểm nguyên $x$ trên trục số sao cho giá trị hàm $f_k(x)$ là nhỏ nhất có thể.

Hàm $f_k(x)$ được định nghĩa như sau:

• Lập danh sách khoảng cách $d_1,d_2,\dots ,d_n$ với $d_i=|a_i-x|$;
• Sắp xếp danh sách $d$ theo thứ tự không giảm;
• Lấy phần tử $d_{k+1}$ (phần tử nhỏ thứ $k+1$) làm kết quả.

Nói cách khác, $f_k(x)$ là khoảng cách nhỏ thứ $k+1$ từ $x$ đến các điểm đã cho.

Nếu có nhiều điểm $x$ cho giá trị nhỏ nhất, bạn có thể in ra bất kỳ điểm nào trong số đó.

Dữ liệu vào

• Dòng đầu chứa một số nguyên $T$ — số truy vấn. Tiếp theo là $2T$ dòng mô tả các truy vấn (các truy vấn độc lập với nhau).
• Dòng đầu của mỗi truy vấn chứa hai số nguyên $n$ và $k$.
• Dòng thứ hai của mỗi truy vấn chứa $n$ số nguyên $a_1<a_2<\dots <a_n$.

Dữ liệu ra

In ra $T$ số nguyên — mỗi số là một điểm $x$ ứng với giá trị $f_k(x)$ nhỏ nhất cho truy vấn tương ứng.

Ràng buộc

• $1\le T\le 2·{10}^5$
• $1\le n\le 2·{10}^5$, $0\le k<n$
• $1\le a_1<a_2<\dots <a_n\le {10}^9$
• Tổng $n$ trên tất cả các truy vấn không vượt quá $2·{10}^5$.

Ví dụ