题目描述

给一个环形序列 A[1],A[2],A[3]......A[n]. 环形序列的意思是 A[n]是A[1]的左邻居, 并且A[1]是A[n] 的右邻居.

现在你的任务就是找出Max-K-sub-序列的最大值. Max-K-sub序列的意思是在环形序列中的一个连续的且长度不超过K的子序列.

输入要求

第一行输入一个数T(1<=T<=100) ,表示有T组测试. 
对于每组测试，先输入两个数N , K(1<=N<=100000 , 1<=K<=N),接下来输入N个数（A[1]、A[2]、……、A[N]，且-1000<=A[i]<=1000）

输出要求

对于每组测试结果输出三个数（Max-K-sub-序列的值、Max-K-sub-序列的起始位置、Max-K-sub-序列的末位置）。
结果不唯一，则输出起始位置小的，如果结果仍不唯一输出长度短的序列。

输入样例

4
6 3
6 -1 2 -6 5 -5
6 4
6 -1 2 -6 5 -5
6 3
-1 2 -6 5 -5 6
6 6
-1 -1 -1 -1 -1 -1

输出样例

7 1 3
7 1 3
7 6 2
-1 1 1

提示

来源

NBU OJ