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, \dots, 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, \dots, 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 \le T \le 2 \cdot 10^5$) — number of queries. Next $2 \cdot T$ lines contain descriptions of queries. All queries are independent. 

The first line of each query contains two integers $n$, $k$ ($1 \le n \le 2 \cdot 10^5$, $0 \le k < n$) — the number of points and constant $k$.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_1 < a_2 < \dots < a_n \le 10^9$) — points in ascending order.

It's guaranteed that $\sum{n}$ doesn't exceed $2 \cdot 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

Difficulty: interview

Starter code:

Solutions:
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N, K = list(map(int, input().split()))
    A = [int(a) for a in input().split()]
    B = [A[i+K]-A[K] for i in range(N-K)]
    mi = 10**20
    mx = -1
    for i in range(N-K):
        if A[i+K]-A[i] < mi:
            mi = A[i+K]-A[i]
            mx = (A[i+K]+A[i]) // 2
    
    print(mx)



def main():
    buf = input()
    T = int(buf)
    n = []
    k = []
    a = []
    for i in range(T):
        buf = input()
        buflist = buf.split()
        n.append(int(buflist[0]))
        k.append(int(buflist[1]))
        buf = input()
        buflist = buf.split()
        a.append(list(map(int, buflist)))
    for i in range(T):
        a[i].sort()
    for i in range(T):
        minimum_point = (a[i][0] + a[i][k[i]]) // 2
        minimum_value = max(abs(a[i][0] - minimum_point), abs(a[i][k[i]] - minimum_point))
        for j in range(1, n[i]-k[i]):
            window_minimum_point = (a[i][j] + a[i][k[i]+j]) // 2
            window_minimum_value = max(abs(a[i][j] - window_minimum_point), abs(a[i][k[i]+j] - window_minimum_point))
            if window_minimum_value < minimum_value:
                minimum_point = window_minimum_point
                minimum_value = window_minimum_value
        print(minimum_point)

def __starting_point():
    main()

__starting_point()

def funk():
    nonlocal m
    n, k = map(int, input().split())
    mass = [int(i) for i in input().split()]
    x = 0
    minn = 10 ** 9
    for i in range(n - k):
        q = mass[i]
        j = mass[i + k]
        if (j - q) < minn:
            minn, x = (j - q), (j + q) // 2
    m.append(x)    

t = int(input())
m = []
for i in range(t):
    funk()
    
for i in m:
    print(i)

import sys
input = sys.stdin.readline

Query=int(input())

for query in range(Query):
    n,k=list(map(int,input().split()))
    A=list(map(int,input().split()))

    A.sort()

    L=10**15

    for i in range(k,n):
        if A[i]-A[i-k]<L:
            L=A[i]-A[i-k]
            ANS=(A[i]+A[i-k])//2

    print(ANS)


import sys
input = sys.stdin.readline


t = int(input())
li = [list(map(int, input().split())) for i in range(2*t)]
for i in range(t):
    n, k = li[i*2][0], li[i*2][1]
    ans = 10**10
    j = 0
    item = 0
    while j + k < n:
        if -((-(li[i*2+1][j+k] - li[i*2+1][j])) // 2) < ans:
            ans = -((-(li[i*2+1][j+k] - li[i*2+1][j])) // 2)
            item = (li[i*2+1][j+k] + li[i*2+1][j])//2
        j += 1
    print(item)



import sys
input = sys.stdin.readline


class Problem:
    def __init__(self):
        pass

    def solve(self):
        self._solve()

    def _solve(self):
        t = int(input())
        for _ in range(t):
            n, k = [int(item) for item in input().split()]
            a = [int(item) for item in input().split()]
            a.sort()
            mn = float('inf')
            idx = -1
            for i in range(n - k):
                if a[i + k] - a[i] < mn:
                    mn = a[i + k] - a[i]
                    idx = i
            print((a[idx] + a[idx + k]) >> 1)


def main():
    problem = Problem()
    problem.solve()


def __starting_point():
    main()

__starting_point()

import sys
input = sys.stdin.readline
import bisect
T = int(input())
for _ in range(T):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = 10000000000
    for i in range(n-k):
        if ans > a[i+k]-a[i]:
            ansindex = i
            ans = a[i+k]-a[i]
    print(a[ansindex]+ans//2)


# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve2():
    n, k = list(map(int, input().split()))
    L = list(map(int, input().split()))
    ans = float('inf')
    ans_x = -1
    for i in range(n-k):
        l = L[i]
        r = L[i+k]
        tmp = (r+l)//2
        tmp_ans = max(r-tmp, tmp-l)
        if ans > tmp_ans:
            ans = tmp_ans
            ans_x = tmp
    print(ans_x)


n = int(input())
for _ in range(n):
    solve2()


import sys

T = int(sys.stdin.readline().strip())
for t in range (0, T):
    n, k = list(map(int,sys.stdin.readline().strip().split()))
    a = list(map(int,sys.stdin.readline().strip().split()))
    i = 0
    j = k
    M = 10 ** 10
    while j < n:
        if a[j] - a[i] < M:
            M = a[j] - a[i]
            x = (a[j] + a[i]) // 2 + (a[j] + a[i]) % 2
        i = i + 1
        j = j + 1
    print(x)

def fk(n, l1, k):
    if (k==0):
        return str(l1[0])
    mi = l1[-1] - l1[0] + 1
    p = 0
    for i in range(n-k):
        if (l1[i+k]-l1[i] < mi):
            mi = l1[i+k]-l1[i]
            p = (l1[i+k] + l1[i]) >> 1
    return str(p)

t = int(input())
l = []
for _ in range(t):
    n, k = list(map(int, input().split()))
    l1 = list(map(int, input().split()))
    l.append(fk(n, l1, k))
print('\n'.join(l))

t = int(input())

answers = []

for i in range(t):
    n,k = list(map(int, input().split()))
    a = list(map(int, input().split()))

    min_koor = 0
    min_dist = (a[n-1]-a[0])

    for j in range(0, n-k):
        if (a[j+k]-a[j]<=min_dist):
            min_dist=a[j+k]-a[j]
            min_koor = (a[j]+a[j+k])/2
    answers.append(min_koor)
for i in answers:
    print(int(i))
        


t = int(input())
Ans = []

for _ in range(t):
    n,k = map(int,input().split())
    A = list(map(int,input().split()))
    mini = 100000000000
    for i in range(n-k):
        y1 = (-A[i]+A[i+k]-1)/2
        y2 = (-A[i]+A[i+k])/2
        if float.is_integer(y1):
            if mini > y1+1:
                ans = A[i] + y1
                mini = y1 + 1
        elif float.is_integer(y2):
            if mini > y2:
                ans = A[i] + y2
                mini = y2
    Ans.append(int(ans))

print(*Ans,sep = "\n")
    

t    = int(input()) 
s    = ''
for _ in range(t):
    n, k = map(int, input().split())
    a    = list(map(int, input().split()))
    Min  = 1000000001
    ans  = a[0]

    for x, y in zip(a[:-k], a[k:]):
        if y - x < Min:
            ans = ( x + y ) // 2
            Min = y - x
    s += str(ans) + '\n'
print(s)    

T = int(input())
import sys
res = []

for t in range(T):
    N, K = map(int, sys.stdin.readline().split())
    a_list = list(map(int, sys.stdin.readline().split()))
    if N == 1:
        res.append(a_list[0])
        continue
    ans = float("inf")
    ans_i = -1
    for i in range(N - K):
        tmp = abs(a_list[i + K] - a_list[i])
        if ans > tmp:
            ans =tmp
            ans_i = i
    res.append((a_list[ans_i + K] + a_list[ans_i]) // 2)

for r in res:
    print(r)

import sys
input = sys.stdin.readline


def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))



q=nn()


for _ in range(q):
	n, k=mi()

	l=lm()

	m=float('Inf')

	
	for i in range(0, n-k):
		
		
		if l[i+k]-l[i]<m:
			m=l[i+k]-l[i]
			x=(l[i+k]+l[i])//2			
			
	
	print(x)


def solve(points,k,res):
    if k == 0:
        res.append(points[0])
        return
    min_diff = float('inf')
    n = len(points)
    for i in range(n-k):
        p1 = points[i]
        p2 = points[i+k]
        avg = (p1+p2)//2
        diff = max(abs(avg-p1),abs(avg-p2))

        if diff < min_diff:
            ans = avg
            min_diff = diff

    res.append(ans)
            

def main():
    t = int(input())
    res = []
    for i in range(t):
        n,k = list(map(int,input().split()))
        points = list(map(int,input().split()))
        solve(points,k,res)

    for i in res:
        print(i)

main()


def fk(n, l1, k):
    if (k==0):
        return str(l1[0])
    mi = l1[-1] - l1[0]
    p = (l1[-1] + l1[0]) >> 1
    for i in range(n-k):
        if (l1[i+k]-l1[i] < mi):
            mi = l1[i+k]-l1[i]
            p = (l1[i+k] + l1[i]) >> 1
    return str(p)

t = int(input())
l = []
for _ in range(t):
    n, k = list(map(int, input().split()))
    l1 = list(map(int, input().split()))
    l.append(fk(n, l1, k))
print('\n'.join(l))

import sys
input = sys.stdin.readline
import bisect
T = int(input())
for _ in range(T):
    n, k = list(map(int, input().split()))
    a = list(map(int, input().split()))
    ans = 10000000000
    for i in range(n-k):
        if ans > a[i+k]-a[i]:
            ansindex = i
            ans = a[i+k]-a[i]
    print(a[ansindex]+ans//2)


t=int(input())
out=[0]*t
for u in range(t):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    a.sort()
    best=float("inf")
    coord=None
    for i in range(n-k):
        if a[i+k]-a[i]<best:
            coord=(a[i+k]+a[i])//2
            best=a[i+k]-a[i]
    out[u]=coord
print(*out,sep='\n')

import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
    n,k = map(int, input().split())
    aa = list(map(int, input().split()))
    best = 10000000000
    for i in range(n-k):
        if aa[i+k] - aa[i] < best:
            best = aa[i+k] - aa[i]
            bestpos = i
    print(aa[bestpos] + best//2)