#include<bits/stdc++.h> using namespace std; #define N 500005 #define ll int ll t,n,k; ll a[N]; ll q1[N],q2[N],p1[N],p2[N],head1,rear1,head2,rear2; ll Ans1,Ans2; ll Max=-1000000009,Min=1000000009; bool check1(ll x){ rear1=rear2=head1=head2=0; int cnt=0; for(int i=1;i<=n;i++){ while(head1<rear1 && a[i]>=q1[rear1-1]) rear1--; q1[rear1]=a[i]; p1[rear1++]=i; while(p1[head1]<=i-n+k-1) head1++; while(head2<rear2 && a[i]<=q2[rear2-1]) rear2--; q2[rear2]=a[i]; p2[rear2++]=i; while(p2[head2]<=i-n+k-1) head2++; if(q1[head1]-q2[head2]>=x && i>=n-k+1) cnt++; //cout<<q1[head1]<<' '<<head1<<' '<<rear1<<' '<<q2[head2]<<' '<<head2<<' '<<rear2<<endl; } if(cnt>=k) return 1; else return 0; } bool check2(ll x){ rear1=rear2=head1=head2=0; int cnt=0; for(int i=1;i<=n;i++){ while(head1<rear1 && a[i]>=q1[rear1-1]) rear1--; q1[rear1]=a[i]; p1[rear1++]=i; while(p1[head1]<=i-x) head1++; while(head2<rear2 && a[i]<=q2[rear2-1]) rear2--; q2[rear2]=a[i]; p2[rear2++]=i; while(p2[head2]<=i-x) head2++; if(q1[head1]-q2[head2]>=Ans1 && i>=x) cnt++; } if(cnt>=k) return 1; else return 0; } int main(){ //freopen("choose.in","r",stdin); //freopen("choose.out","w",stdout); cin>>t; while(t--){ Ans1=Ans2=0; cin>>n>>k; for(int i=1;i<=n;i++){ cin>>a[i]; } ll l=0,r=2000000000,mid; while(l<=r){ mid=l+(r-l)/2; //cout<<mid<<endl; if(check1(mid)){ Ans1=mid; l=mid+1; }else r=mid-1; //cout<<endl; } l=1,r=n-k+1; while(l<=r){ mid=l+(r-l)/2; if(check2(mid)){ Ans2=mid; r=mid-1; }else l=mid+1; } cout<<Ans1<<' '<<Ans2<<endl; } return 0; }