题目描述

Alice 和 Bob 在一个长度为 $n$ 的序列 $a$ 上博弈。Alice 先手，双方交替进行操作：

• 选择一个长度为 $k$ 的连续区间，删掉其中 $k-1$ 个元素。

保证 $n-1$ 是 $k-1$ 的正整数倍，因此最终只会剩下一个数。

Alice 想使最终剩下的数尽可能小，Bob 想使最终剩下的数尽可能大。假设双方都采用最优策略，请求出最终剩下的数。

输入格式

第一行一个正整数 $T$，表示数据组数。

对于每组数据：

• 第一行两个正整数 $n,k$；
• 第二行 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出 $T$ 行，每行一个正整数，表示对应数据的答案。

数据范围

测试点编号	$n\le$	$k\le$	$\sum n\le$
$1\sim 2$	$10$	$n$	$100$
$3\sim 4$	$10^5$	$2$	$10^6$
$5\sim 8$	$1000$	$n$	$5000$
$9\sim 10$	$10^5$		$10^6$

对于全部数据：

$$n\le 10^5,\qquad \sum n\le 10^6,\qquad 2\le k\le n,$$$$a_i\le 10^9,\qquad k-1\mid n-1.$$