#include <bits/stdc++.h>
using namespace std;
long long dx[] = {1, -1, 0, 0};
long long dy[] = {0, 0, 1, -1};
const long long inf = 1e18 + 5;
const long long sz = 2e5 + 5, mod = 998244353;
long long t, n, m, k, q;
long long power(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
long long Inv(long long a) { return power(a, mod - 2); }
vector<vector<long long> > gr(sz);
vector<long long> level(sz, 0);
map<long long, long long> mp;
vector<long long> child(sz, 0);
long long DFS1(long long s, long long p, long long lev) {
  level[s] = lev;
  long long ans = 1;
  for (auto i : gr[s]) {
    if (i != p) ans += DFS1(i, s, lev + 1);
  }
  child[s] = ans;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  t = 1;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    vector<long long> v(n);
    for (auto &i : v) cin >> i;
    sort(v.begin(), v.end());
    if (k == 0) {
      cout << v[0] << "\n";
      continue;
    }
    long long l = 0, r = k;
    long long mn = v[r] - v[l];
    for (long long i = k; i < n; i++) {
      if (v[i] - v[i - k] < mn) {
        l = i - k;
        r = i;
        mn = v[i] - v[i - k];
      }
    }
    cout << (v[l] + v[r]) / 2 << "\n";
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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 dx[] = {1, -1, 0, 0};
long long dy[] = {0, 0, 1, -1};
const long long inf = 1e18 + 5;
const long long sz = 2e5 + 5, mod = 998244353;
long long t, n, m, k, q;
long long power(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b & 1) {
      ans = (ans * a) % mod;
    }
    a = (a * a) % mod;
    b >>= 1;
  }
  return ans;
}
long long Inv(long long a) { return power(a, mod - 2); }
vector<vector<long long> > gr(sz);
vector<long long> level(sz, 0);
map<long long, long long> mp;
vector<long long> child(sz, 0);
long long DFS1(long long s, long long p, long long lev) {
  level[s] = lev;
  long long ans = 1;
  for (auto i : gr[s]) {
    if (i != p) ans += DFS1(i, s, lev + 1);
  }
  child[s] = ans;
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  t = 1;
  cin >> t;
  while (t--) {
    cin >> n >> k;
    vector<long long> v(n);
    for (auto &i : v) cin >> i;
    sort(v.begin(), v.end());
    if (k == 0) {
      cout << v[0] << "\n";
      continue;
    }
    long long l = 0, r = k;
    long long mn = v[r] - v[l];
    for (long long i = k; i < n; i++) {
      if (v[i] - v[i - k] < mn) {
        l = i - k;
        r = i;
        mn = v[i] - v[i - k];
      }
    }
    cout << (v[l] + v[r]) / 2 << "\n";
  }
  return 0;
}

```