#include <bits/stdc++.h>
using namespace std;
int read() {
  int X = 0, p = 1;
  char c = getchar();
  for (; c > '9' || c < '0'; c = getchar())
    if (c == '-') p = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
  return X * p;
}
const int N = 2e5 + 5;
int n, a[N], T, k;
int main() {
  T = read();
  for (; T; T--) {
    n = read();
    k = read() + 1;
    int ans = 1e9 + 7, p = 0;
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n - k + 1; ++i) {
      int l = a[i], r = a[i + k - 1];
      int L = (i == 1 ? a[1] : (r + a[i - 1] + 1) / 2);
      int R = (i + k - 1 == n ? a[n] : (l + a[i + k]) / 2);
      if ((r - l) % 2 == 0) {
        int minn, mid = (l + r) >> 1;
        if (mid <= R && mid >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid;
        } else if (r - R > L - l) {
          minn = r - R;
          if (minn < ans) ans = minn, p = R;
        } else {
          minn = L - l;
          if (minn < ans) ans = minn, p = L;
        }
      } else {
        int minn, mid = (l + r) >> 1;
        if (mid <= R && mid >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid;
        } else if (mid + 1 <= R && mid + 1 >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid + 1;
        } else if (r - R > L - l) {
          minn = r - R;
          if (minn < ans) ans = minn, p = R;
        } else {
          minn = L - l;
          if (minn < ans) ans = minn, p = L;
        }
      }
    }
    printf("%d\n", p);
  }
}

### 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;
int read() {
  int X = 0, p = 1;
  char c = getchar();
  for (; c > '9' || c < '0'; c = getchar())
    if (c == '-') p = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) X = X * 10 + c - '0';
  return X * p;
}
const int N = 2e5 + 5;
int n, a[N], T, k;
int main() {
  T = read();
  for (; T; T--) {
    n = read();
    k = read() + 1;
    int ans = 1e9 + 7, p = 0;
    for (int i = 1; i <= n; ++i) a[i] = read();
    for (int i = 1; i <= n - k + 1; ++i) {
      int l = a[i], r = a[i + k - 1];
      int L = (i == 1 ? a[1] : (r + a[i - 1] + 1) / 2);
      int R = (i + k - 1 == n ? a[n] : (l + a[i + k]) / 2);
      if ((r - l) % 2 == 0) {
        int minn, mid = (l + r) >> 1;
        if (mid <= R && mid >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid;
        } else if (r - R > L - l) {
          minn = r - R;
          if (minn < ans) ans = minn, p = R;
        } else {
          minn = L - l;
          if (minn < ans) ans = minn, p = L;
        }
      } else {
        int minn, mid = (l + r) >> 1;
        if (mid <= R && mid >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid;
        } else if (mid + 1 <= R && mid + 1 >= L) {
          minn = r - mid;
          if (minn < ans) ans = minn, p = mid + 1;
        } else if (r - R > L - l) {
          minn = r - R;
          if (minn < ans) ans = minn, p = R;
        } else {
          minn = L - l;
          if (minn < ans) ans = minn, p = L;
        }
      }
    }
    printf("%d\n", p);
  }
}

```