#P18074. The Messenger

The Messenger

The Messenger

题目描述

给定序列的前 nn 项 a1,a2,…,ana_1,a_2,\ldots,a_n。对于 k>nk>n,定义

ak=max⁡{ai−aj∣k−n≤i,j<k}.a_k=\max\{a_i-a_j\mid k-n\le i,j<k\}.

也就是说,新的一项等于前面连续 nn 项的最大值减去最小值。求 ama_m。

输入格式

第一行整数 TT,表示测试用例数。每组数据第一行两个整数 n,mn,m,第二行 nn 个整数 a1,…,ana_1,\ldots,a_n。

1≤T≤1041\le T\le10^4,2≤n≤5002\le n\le500,1≤m≤10181\le m\le10^{18},0≤ai≤10180\le a_i\le10^{18}。所有测试用例的 nn 之和不超过 500500。若 m≤nm\le n,答案就是对应的已知初值。

输出格式

每组输出一行一个整数 ama_m。

样例 1

输入

5
3 5
43 47 41
3 6
43 47 41
3 7
43 47 41
3 8
43 47 41
4 200
104857601998244353 1145141919810 3141592653589793 27182818284590452

输出

41
35
35
6
377005672062684