Description

Input

The first line contains single integer $T$ ($1 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent.

The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.

It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 10^5$.

Output

Print $T$ integers — corresponding points $x$ which have minimal possible value of $f_k(x)$. If there are multiple answers you can print any of them.

3
3 2
1 2 5
2 1
1 1000000000
1 0
4

3
500000000
4