#include <bits/stdc++.h>
using namespace std;
const long long RLEN = 1 << 20 | 1;
inline char gc() {
  static char ibuf[RLEN], *ib, *ob;
  (ob == ib) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ob == ib) ? EOF : *ib++;
}
inline long long read() {
  char ch = getchar();
  long long res = 0, f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = getchar();
  return f ? res : -res;
}
const long long N = 200005;
long long T, n, k;
long long a[N];
signed main() {
  T = read();
  while (T--) {
    n = read(), k = read();
    generate(a + 1, a + n + 1, read);
    long long mx = 2e9, pos = a[1];
    for (long long i = 1; i <= n - k; i++) {
      long long now = a[i + k] - a[i];
      if (now <= mx) mx = now, pos = (a[i + k] + a[i]) / 2;
    }
    cout << pos << '\n';
  }
}

### 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;
const long long RLEN = 1 << 20 | 1;
inline char gc() {
  static char ibuf[RLEN], *ib, *ob;
  (ob == ib) && (ob = (ib = ibuf) + fread(ibuf, 1, RLEN, stdin));
  return (ob == ib) ? EOF : *ib++;
}
inline long long read() {
  char ch = getchar();
  long long res = 0, f = 1;
  while (!isdigit(ch)) f ^= ch == '-', ch = getchar();
  while (isdigit(ch)) res = (res + (res << 2) << 1) + (ch ^ 48), ch = getchar();
  return f ? res : -res;
}
const long long N = 200005;
long long T, n, k;
long long a[N];
signed main() {
  T = read();
  while (T--) {
    n = read(), k = read();
    generate(a + 1, a + n + 1, read);
    long long mx = 2e9, pos = a[1];
    for (long long i = 1; i <= n - k; i++) {
      long long now = a[i + k] - a[i];
      if (now <= mx) mx = now, pos = (a[i + k] + a[i]) / 2;
    }
    cout << pos << '\n';
  }
}

```