#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long s = 0, t = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') t = -1;
    c = getchar();
  }
  while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
  return s * t;
}
const int N = 2e5 + 5, ma = 1e9;
struct node {
  int x;
  int is_left;
  bool operator<(const node& rhs) const {
    if (x != rhs.x)
      return x < rhs.x;
    else
      return is_left < rhs.is_left;
  }
} A[N << 1];
int n, k, point[N];
inline int Q(int dis) {
  int tot = 0;
  for (register int i = 1; i <= n; i++) {
    A[++tot].x = max(1, point[i] - dis);
    A[tot].is_left = 1;
    A[++tot].x = point[i] + dis + 1;
    A[tot].is_left = -1;
  }
  sort(A + 1, A + tot + 1);
  int sum = 0;
  for (register int i = 1; i <= tot; i++) {
    sum += A[i].is_left;
    if (sum >= k + 1) return A[i].x;
  }
  return -1;
}
int main() {
  int t = read();
  while (t--) {
    n = read(), k = read();
    for (register int i = 1; i <= n; i++) point[i] = read();
    int l = 0, r = ma, mid, ans;
    while (l < r) {
      mid = (l + r) >> 1;
      if (Q(mid) != -1)
        r = mid;
      else
        l = mid + 1;
    }
    cout << Q(l) << endl;
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;
inline long long read() {
  long long s = 0, t = 1;
  char c = getchar();
  while (!isdigit(c)) {
    if (c == '-') t = -1;
    c = getchar();
  }
  while (isdigit(c)) s = s * 10 + c - 48, c = getchar();
  return s * t;
}
const int N = 2e5 + 5, ma = 1e9;
struct node {
  int x;
  int is_left;
  bool operator<(const node& rhs) const {
    if (x != rhs.x)
      return x < rhs.x;
    else
      return is_left < rhs.is_left;
  }
} A[N << 1];
int n, k, point[N];
inline int Q(int dis) {
  int tot = 0;
  for (register int i = 1; i <= n; i++) {
    A[++tot].x = max(1, point[i] - dis);
    A[tot].is_left = 1;
    A[++tot].x = point[i] + dis + 1;
    A[tot].is_left = -1;
  }
  sort(A + 1, A + tot + 1);
  int sum = 0;
  for (register int i = 1; i <= tot; i++) {
    sum += A[i].is_left;
    if (sum >= k + 1) return A[i].x;
  }
  return -1;
}
int main() {
  int t = read();
  while (t--) {
    n = read(), k = read();
    for (register int i = 1; i <= n; i++) point[i] = read();
    int l = 0, r = ma, mid, ans;
    while (l < r) {
      mid = (l + r) >> 1;
      if (Q(mid) != -1)
        r = mid;
      else
        l = mid + 1;
    }
    cout << Q(l) << endl;
  }
  return 0;
}

```