#include <bits/stdc++.h>
using namespace std;
long long n, m, k;
long long read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
inline void print(long long *f, long long len) {
  for (long long i = 0; i < len; i++) printf("%lld ", f[i]);
  puts("");
}
long long a[1010101];
signed main() {
  long long T = read();
  while (T--) {
    n = read(), k = read();
    for (long long i = 1, iend = n; i <= iend; ++i) a[i] = read();
    long long mn = 101010010100, pos;
    for (long long i = 1, iend = n - k; i <= iend; ++i) {
      if (a[i + k] - a[i] < mn)
        mn = a[i + k] - a[i], pos = a[i] + (a[i + k] - a[i]) / 2;
    }
    cout << pos << endl;
  }
}

### 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 n, m, k;
long long read() {
  long long s = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    s = s * 10 + ch - '0';
    ch = getchar();
  }
  return s * f;
}
inline void print(long long *f, long long len) {
  for (long long i = 0; i < len; i++) printf("%lld ", f[i]);
  puts("");
}
long long a[1010101];
signed main() {
  long long T = read();
  while (T--) {
    n = read(), k = read();
    for (long long i = 1, iend = n; i <= iend; ++i) a[i] = read();
    long long mn = 101010010100, pos;
    for (long long i = 1, iend = n - k; i <= iend; ++i) {
      if (a[i + k] - a[i] < mn)
        mn = a[i + k] - a[i], pos = a[i] + (a[i + k] - a[i]) / 2;
    }
    cout << pos << endl;
  }
}

```