#include <bits/stdc++.h>
using namespace std;
struct IO {
  static const int Siz = 1 << 13;
  char ibuf[Siz], *ips = ibuf + Siz - 1;
  char obuf[Siz], *ops = obuf;
  ~IO() { o(); }
  void i() {
    fread(ibuf, 1, Siz, stdin);
    ips = ibuf;
  }
  void o() {
    fwrite(obuf, 1, ops - obuf, stdout);
    ops = obuf;
  }
  void flush() {
    o();
    fflush(stdout);
  }
  int getchar() {
    if (ips == ibuf + Siz - 1) i();
    return *ips++;
  }
  void putchar(int x) {
    if (ops == obuf + Siz) o();
    *ops++ = x;
  }
  void gets(char* s) {
    for (; !isspace(*s++ = getchar());)
      ;
  }
  void puts(char* s) {
    for (; *s; putchar(*s++))
      ;
  }
} io;
int read() {
  int x = 0, f = 1, c = io.getchar();
  for (; !isdigit(c); c = io.getchar())
    if (c == 45) f ^= 1;
  for (; isdigit(c); c = io.getchar()) x = x * 10 + c - 48;
  return f ? x : -x;
}
void write(int x) {
  int stk[20], tp = 0;
  if (x < 0) io.putchar(45), x = -x;
  if (!x) io.putchar(48);
  for (; x; stk[tp++] = x % 10, x /= 10)
    ;
  for (; tp; io.putchar(48 + stk[--tp]))
    ;
}
int a[1 << 20];
int cnt[1 << 20];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int lb = 0, rb = 1e9;
    int ans = 0;
    auto chk = [&](int md) {
      bool ok = 0;
      vector<int> v;
      for (int i = 0; i < n; ++i) {
        v.push_back(a[i] - md);
        v.push_back(a[i] + md + 1);
      }
      sort(v.begin(), v.end());
      v.erase(unique(v.begin(), v.end()), v.end());
      int m = v.size();
      for (int i = 0; i < m; ++i) cnt[i] = 0;
      for (int i = 0; i < n; ++i) {
        cnt[lower_bound(v.begin(), v.end(), a[i] - md) - v.begin()]++;
        cnt[lower_bound(v.begin(), v.end(), a[i] + md + 1) - v.begin()]--;
      }
      for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
      for (int i = 0; i < m; ++i)
        if (cnt[i] > k) {
          ok = 1, ans = v[i];
          break;
        }
      return ok;
    };
    for (; lb < rb;) {
      int md = lb + rb >> 1;
      if (chk(md))
        rb = md;
      else
        lb = md + 1;
    }
    chk(lb);
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Please formulate 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;
struct IO {
  static const int Siz = 1 << 13;
  char ibuf[Siz], *ips = ibuf + Siz - 1;
  char obuf[Siz], *ops = obuf;
  ~IO() { o(); }
  void i() {
    fread(ibuf, 1, Siz, stdin);
    ips = ibuf;
  }
  void o() {
    fwrite(obuf, 1, ops - obuf, stdout);
    ops = obuf;
  }
  void flush() {
    o();
    fflush(stdout);
  }
  int getchar() {
    if (ips == ibuf + Siz - 1) i();
    return *ips++;
  }
  void putchar(int x) {
    if (ops == obuf + Siz) o();
    *ops++ = x;
  }
  void gets(char* s) {
    for (; !isspace(*s++ = getchar());)
      ;
  }
  void puts(char* s) {
    for (; *s; putchar(*s++))
      ;
  }
} io;
int read() {
  int x = 0, f = 1, c = io.getchar();
  for (; !isdigit(c); c = io.getchar())
    if (c == 45) f ^= 1;
  for (; isdigit(c); c = io.getchar()) x = x * 10 + c - 48;
  return f ? x : -x;
}
void write(int x) {
  int stk[20], tp = 0;
  if (x < 0) io.putchar(45), x = -x;
  if (!x) io.putchar(48);
  for (; x; stk[tp++] = x % 10, x /= 10)
    ;
  for (; tp; io.putchar(48 + stk[--tp]))
    ;
}
int a[1 << 20];
int cnt[1 << 20];
int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d", &a[i]);
    int lb = 0, rb = 1e9;
    int ans = 0;
    auto chk = [&](int md) {
      bool ok = 0;
      vector<int> v;
      for (int i = 0; i < n; ++i) {
        v.push_back(a[i] - md);
        v.push_back(a[i] + md + 1);
      }
      sort(v.begin(), v.end());
      v.erase(unique(v.begin(), v.end()), v.end());
      int m = v.size();
      for (int i = 0; i < m; ++i) cnt[i] = 0;
      for (int i = 0; i < n; ++i) {
        cnt[lower_bound(v.begin(), v.end(), a[i] - md) - v.begin()]++;
        cnt[lower_bound(v.begin(), v.end(), a[i] + md + 1) - v.begin()]--;
      }
      for (int i = 1; i < m; ++i) cnt[i] += cnt[i - 1];
      for (int i = 0; i < m; ++i)
        if (cnt[i] > k) {
          ok = 1, ans = v[i];
          break;
        }
      return ok;
    };
    for (; lb < rb;) {
      int md = lb + rb >> 1;
      if (chk(md))
        rb = md;
      else
        lb = md + 1;
    }
    chk(lb);
    printf("%d\n", ans);
  }
  return 0;
}

```