Problem Description

For a sequence \( a \) of length \( n \), the range of \( a \) is defined as the difference between its maximum and minimum values. Let \( C(a, l, r) \) represent the continuous subsequence \( [a_l, a_{l+1}, \dots, a_r] \), where \( 1 \le l \le r \le n \).

Given a sequence \( a \) of length \( n \), you need to select \( k \) different continuous subsequences of length \( L \) each, \( 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 value of \( X \) and also the minimum value of \( L \) such that \( X \) is maximized.

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 \) and \( k \).
• The second line contains \( n \) integers \( a_1, a_2, \dots, a_n \).

Output Format

For each test case:

• Output one line containing two integers \( X \) and \( L \), representing the maximum range and the minimum subsequence length respectively.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4 5
3 4
2 3

Sample Input #2

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

Sample Output #2

2 5
1 2

Notes

[Sample 1 Explanation]

• When \( k = 1 \), the maximum range is no more than 4, and one of the shortest length solutions is \([1, 2, 3, 4, 5]\).
• When \( k = 2 \), the maximum range is no more than 3, and one of the shortest length solutions is \([1, 2, 3, 4], [2, 3, 4, 5]\).
• When \( k = 3 \), the maximum range is no more than 2, and one of the shortest length solutions is \([1, 2, 3], [2, 3, 4], [3, 4, 5]\).

[Data Range and Constraints]

This problem uses subtask testing.

For 100% of the data, \( 1 \le T \le 10 \), \( 1 \le n \le 10^5 \), \( 1 \le k \le n \), \( -10^9 \le a_i \le 10^9 \).

见题面 Input 部分

见题面 Output 部分