ll@T;rep(T){ll@N,@L,@K,@A[N],j,x,y,p=-1,P=L;sort(A,A+N);while(p+1<P){ll m=(p+P)/2,l=-P,r=1,b=1;rep(i,N+1){j=i+K-1;if((x=A[j%N]+j/N*L-m)<(y=A[i%N]+i/N*L+m+1)){if(l+P)b&=x<r;else l=x;r=y;}}(l+L<r&b?P:p)=m;};wt(P);}