#P16714. Tspin single

Tspin single

题目描述

Alice 和 Bob 在一个长度为 nn 的序列 aa 上博弈。Alice 先手,双方交替进行操作:

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

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

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

输入格式

第一行一个正整数 TT,表示数据组数。

对于每组数据:

  • 第一行两个正整数 n,kn,k;
  • 第二行 nn 个正整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

输出 TT 行,每行一个正整数,表示对应数据的答案。

数据范围

测试点编号 n≤n\le k≤k\le ∑n≤\sum n\le
1∼21\sim 2 1010 nn 100100
3∼43\sim 4 10510^5 22 10610^6
5∼85\sim 8 10001000 nn 50005000
9∼109\sim 10 10510^5 10610^6

对于全部数据:

$$n\le 10^5,\qquad \sum n\le 10^6,\qquad 2\le k\le n,$$ai≤109,k−1∣n−1.a_i\le 10^9,\qquad k-1\mid n-1.