First, see minimize y − x y-x y − x this thing, decisive two points y − x y-x y − x, obviously, if the interval is longer, it must be shorter, and then enumeration x x x is then obtained [ x , y ] [x,y] [x,y], the next thing is to judge a certain interval [ x , y ] [x,y] Whether [x,y] is legal.

Let's cut it into k k Segment k is converted to as many segments as possible, because if t t The segmentation of segment t is legal. We merge the last two intervals, which is t − 1 t-1 t − 1.

We will a i a_i ai ， reassign, if a i ∈ [ x , y ] a_i \in [x,y] ai ∈ [x,y] is then assigned to 1, otherwise it is - 1. In this way, we are divided k k k-segment interval a i a_i The sum of ai ＾ can be positive. Since this is interval summation, make a prefix sum s i = ∑ j = 1 i a j s_i=\sum\limits_{j=1}^ia_j si = j=1 Σ i aj, the condition becomes s r − s l − 1 > 0 , s r > s l − 1 s_r-s_{l-1}\gt0,s_r>s_{l-1} sr​−sl−1​>0,sr​>sl−1​， l − 1 l-1 l − 1 is the right endpoint of the previous interval, that is, we are looking for one s s The ascending subsequence of s and its length is k + 1 k+1 k+1, starting from s 0 = 0 s_0=0 s0 = 0, end point is s n s_n sn​. So after all this, I found that the complexity was still not good.

But we found that we could actually rescue it. We found that s s s has a wonderful property, which is ∣ s i − s i − 1 ∣ = 1 |s_i-s_{i-1}|=1 ∣ si − si − 1 ∣ = 1, so if s s In s x > 0 x>0 x> 0, then s s s there must be 0 , 1 , 2 ⋯ x − 2 , x − 1 0,1,2\cdots x-2,x-1 0,1,2 * x − 2,x − 1, and the subscript exists before it. This longest ascending subsequence can be constructed, only if the middle is a continuous positive integer. The last condition is that the sequence length must be k + 1 k+1 k+1, it's simple, just let s n ≥ k s_n\ge k sn ≥ k is OK. So we only need to calculate one to determine whether the interval combination is legal or not s n s_n sn ， it's over.

review s n s_n sn definition, we make t = ∑ i = 1 n [ a i ∈ [ x , y ] ] t=\sum\limits_{i=1}^n[a_i \in [x,y]] t=i=1 Σ n [ai ∈ [x,y]], obviously s n = t − ( n − t ) = 2 t − n s_n=t-(n-t)=2t-n sn = t − (n − t)=2t − n, that is, in [ x , y ] [x,y] Subtract the absent from the number of [x,y]. We then use a prefix and the number of numbers that are convenient to query in a range to calculate s n s_n sn, so the question is over, isn't it?

At that time, I thought it would be gone, but I found that the problem asked me to ask for a plan. I was stupid. It's actually simple. Now that you know it [ x , y ] [x,y] [x,y], we can solve it according to the ascending subsequence, or we can be greedy directly, because it ensures [ x , y ] [x,y] [x,y] is legal, so let's divide it when the sum of intervals is positive. Obviously, this is right.

enumeration [ x , y ] [x,y] [x,y] it seems that you can also use double pointers, but I can't.

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define cmin(a, b) (a)=min((a), (b))
#define cmax(a, b) (a)=max((a), (b))
#define mem(a, x) memset(a, x, sizeof(a))
#define rps(i, b, e) for(int i=(b);i<=(e);i++)
#define prs(i, e, b) for(int i=(e);i>=(b);i--)
#define rpg(i, g, x) for(int i=g.head[x];i;i=g.e[i].nxt)
#define opf(s) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
template<class T>
inline void read(T &x) {
	x=0;
	bool f=false;
	char c=getchar();
	while(!isdigit(c))f|=(c=='-'), c=getchar();
	while(isdigit(c))x=x*10+(c-'0'), c=getchar();
	if(f)x=-x;
}
const int NR=2e5+10;
int T, n, k, a[NR], s[NR];
int chk(int dif) {
	rps(l, 1, n-dif+1)
		if((s[l+dif]-s[l-1])*2-n>=k)
			return l;
	return 0;
}
struct node {
	int id, v, ct;
}st[NR], p[NR];
int top;
int main() {
	read(T);
	while(T--) {
		read(n), read(k);
		mem(s, 0);
		rps(i, 1, n)read(a[i]), s[a[i]]++;
		rps(i, 1, n)s[i]+=s[i-1];
		int l=0, r=n-1, mid, yx=1e9, xx=1e9;
		while(l<=r) {
			mid=l+r>>1;
			int res=chk(mid);
			if(res==0)l=mid+1;
			else yx=mid, xx=res, r=mid-1;
		}
		printf("%d %d\n", xx, xx+yx);
		int yy=xx+yx;
		l=1;
		int subct=0, ns=0;
		rps(i, 1, n) {
			if(a[i]>=xx && a[i]<=yy)ns++;
			else ns--;
			if(ns<=0 || subct+1>=k)continue;
			printf("%d %d\n", l, i);
			l=i+1, subct++, ns=0;
		}
		printf("%d %d\n", l, n);
	}
	return 0;
}