human
At first, there was a legend related to the name of the problem, but now it's just a formal statement.

You are given n points a_1, a_2, ..., a_n on the OX axis. Now you are asked to find such an integer point x on OX axis that f_k(x) is minimal possible.

The function f_k(x) can be described in the following way: 

  * form a list of distances d_1, d_2, ..., d_n where d_i = |a_i - x| (distance between a_i and x).

  * sort list d in non-descending order.

  * take d_{k + 1} as a result. 


If there are multiple optimal answers you can print any of them.

Input

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

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

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

It's guaranteed that ∑{n} doesn't exceed 2 ⋅ 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.

Example

Input

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

Output

3
500000000
4
The above is tricky. Write me a correct solution in PYTHON3.
assistant
#Here is Python code to find such an integer point x on OX axis that f_k(x) is minimal possible.

import sys 
# data = []
# n = 0
# k = 0
# def bins(a, b):
#     if a == b:
#         return a
#     mid = (a+b)//2
#     for i in range(n-k):
#         if data[i+k] <= data[i] + 2 * mid:
#             return bins()
for w in range(int(input())):
    n, k = [int(i) for i in sys.stdin.readline().split()]
    data = [int(i) for i in sys.stdin.readline().split()]
    mn = float('inf')
    x = 0
    for i in range(n-k):
        a = data[i+k] - data[i]
        if a < mn:
            mn = a
            x = i
    print((data[x] + data[x+k])//2 )