Description

Given a sequence $a$ of length $n$.

You need to select $k$ different contiguous subsequences of $a$, all with length $L$ $(1\le L\le n-k+1)$: $C(a,l_1,l_1+L-1),C(a,l_2,l_2+L-1),\dots,C(a,l_k,l_k+L-1)$, where $1\le l_1<l_2< \dots< l_k\le n-L+1$.

Let the minimum range among these $k$ subsequences be $X$. You need to find the maximum possible value of $X$. Also, when $X$ is maximized, you need to find the minimum possible value of $L$.

Input Format

This problem contains multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

• The first line contains two integers $n,k$.
• The second line contains $n$ integers $a_1,a_2,\dots,a_n$.

Output Format

For each test case:

• Output one line with two integers $X,L$, representing the required range and the subsequence length.

3
5 1
1 2 3 4 5
5 2
1 2 3 4 5
5 3
1 2 3 4 5

4 5
3 4
2 3

2
5 1
1 2 2 2 3
5 2
1 2 2 2 3

2 5
1 2

Hint

[Sample 1 Explanation]

• When $k=1$, the maximum possible range is at most $4$. One shortest valid choice is $[1,2,3,4,5]$.
• When $k=2$, the maximum possible range is at most $3$. One shortest valid choice is $[1,2,3,4]$ and $[2,3,4,5]$.
• When $k=3$, the maximum possible range is at most $2$. One shortest valid choice is $[1,2,3]$, $[2,3,4]$, and $[3,4,5]$.

[Constraints and Notes]

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le T\le 10$, $1\le n\le 10^5$, $1\le k\le n$, $-10^9\le a_i\le 10^9$.

Translated by ChatGPT 5