//hdu3415 Max Sum of Max-K-sub-sequence//单调队列//首先想到了预处理出前缀和利用s[i] - s[j]表示(j,i]段的和//之后的问题就转换成了求一个最小的s[j]了，这样就能够单调队列//求最小值。

//队列中维护的是区间的開始的位置j。我们插入队列中的是j-1，由于 //这个时候s[i] - s[j-1]刚好就是[j,i]段闭区间的和 //这里用两种方式实现，一种是stl，一种是手动模拟，两者的速度，測试的 //结果在杭电測试都是一样的，499ms。 // //单调队列的路还长着，继续走吧 #include <cstdio> #include <queue> #include <algorithm> #include <iostream> #include <cstring> using namespace std; typedef long long ll; const int maxn = 1e5 + 8; ll a[maxn*2]; ll sum[maxn*2]; ll x[maxn * 2]; int deq[maxn * 2]; int n,k; int mod; void input(){ scanf("%d%d",&n,&k); for (int i=1;i<=n;i++){ scanf("%lld",&a[i]); } for (int i=n+1;i<=2*n;i++){ a[i] = a[i-n]; } sum[0] = 0; for (int i=1;i<=n;i++){ sum[i] = sum[i-1] + a[i]; } for (int i=1;i<k;i++){ sum[i+n]= sum[i+n-1] + a[i]; } mod = n; n = n + k - 1; } void solve(){ int s,e; int head = 0,tail = 0; ll mx = -1e10; for (int i=1;i<=n;i++){ while(tail > head && sum[i-1]<=sum[deq[tail-1]]) tail--; while(tail > head && deq[head]<i-k) head++; deq[tail++] = i-1; if (sum[i] - sum[deq[head]] > mx){ mx = sum[i] - sum[deq[head]]; s = deq[head] + 1; e = i; } } if (e > mod) e -= mod; printf("%lld %d %d\n",mx,s,e); //printf("%lld %d\n",x[mk],(mk+k)%n); } //void solve(){ // int s,e; // deque<int> deq; // deq.clear(); // ll mx = -1e10; // for (int i=1;i<=n;i++){ // while(!deq.empty() && sum[i-1]<=sum[deq.back()]) // deq.pop_back(); // while(!deq.empty() && deq.front()<i-k) // deq.pop_front(); // deq.push_back(i-1); // if (sum[i] - sum[deq.front()]>mx){ // mx = sum[i] - sum[deq.front()]; // s = deq.front() + 1; // e = i; // } // } // // if (e > mod) // e -= mod; // printf("%lld %d %d\n",mx,s,e); // // //printf("%lld %d\n",x[mk],(mk+k)%n); //} int main(){ //freopen("1.txt","r",stdin); int t; scanf("%d",&t); while(t--){ input(); solve(); } return 0; }