#include <bits/stdc++.h>
using namespace std;
long long int getN(long long int sum) {
  sum = sum * 8;
  sum = sqrt(sum + 1) - 1;
  sum /= 2;
  return sum;
}
long long int apSum(long long int n) {
  long long int a = 1, d = 1;
  long long int res = (2 * a + (n - 1) * d) * n;
  res /= 2;
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isPrime(long long int n) {
  for (long long int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void solveKaro() {
  long long int n, k;
  cin >> n >> k;
  vector<long long int> arr(n);
  for (long long int i = 0; i < arr.size(); i++) {
    cin >> arr[i];
  };
  sort(arr.begin(), arr.end());
  long long int pnt = (arr[k] + arr[0]) / 2;
  long long int ans = max(arr[k] - pnt, pnt - arr[0]);
  for (long long int i = 1; i < n - k; i++) {
    long long int v = (arr[i + k] + arr[i]) / 2;
    long long int d = max(arr[i + k] - v, v - arr[i]);
    if (ans > d) {
      ans = d;
      pnt = v;
    }
  }
  cout << pnt << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int tCase = 1;
  cin >> tCase;
  while (tCase--) {
    solveKaro();
  }
}

### Prompt

Generate a cpp solution to the following problem:

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

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
long long int getN(long long int sum) {
  sum = sum * 8;
  sum = sqrt(sum + 1) - 1;
  sum /= 2;
  return sum;
}
long long int apSum(long long int n) {
  long long int a = 1, d = 1;
  long long int res = (2 * a + (n - 1) * d) * n;
  res /= 2;
  return res;
}
long long int gcd(long long int a, long long int b) {
  if (b == 0) return a;
  return gcd(b, a % b);
}
bool isPrime(long long int n) {
  for (long long int i = 2; i * i <= n; i++) {
    if (n % i == 0) return false;
  }
  return true;
}
void solveKaro() {
  long long int n, k;
  cin >> n >> k;
  vector<long long int> arr(n);
  for (long long int i = 0; i < arr.size(); i++) {
    cin >> arr[i];
  };
  sort(arr.begin(), arr.end());
  long long int pnt = (arr[k] + arr[0]) / 2;
  long long int ans = max(arr[k] - pnt, pnt - arr[0]);
  for (long long int i = 1; i < n - k; i++) {
    long long int v = (arr[i + k] + arr[i]) / 2;
    long long int d = max(arr[i + k] - v, v - arr[i]);
    if (ans > d) {
      ans = d;
      pnt = v;
    }
  }
  cout << pnt << endl;
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int tCase = 1;
  cin >> tCase;
  while (tCase--) {
    solveKaro();
  }
}

```