Range and Partition

Description:

Input:

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$ and the number of subarrays required in the partition.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) where $$$a_i$$$ is the $$$i$$$-th element of the array.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot10^5$$$.

Output:

For each test case, print $$$k+1$$$ lines.

In the first line, print $$$x$$$ and $$$y$$$ — the limits of the found range.

Then print $$$k$$$ lines, the $$$i$$$-th should contain $$$l_i$$$ and $$$r_i$$$ ($$$1\leq l_i \leq r_i \leq n$$$) — the limits of the $$$i$$$-th subarray.

You can print the subarrays in any order.

Sample Input:

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

Sample Output:

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

Note:

In the first test, there should be only one subarray, which must be equal to the whole array. There are $$$2$$$ elements inside the range $$$[1, 2]$$$ and $$$0$$$ elements outside, if the chosen range is $$$[1, 1]$$$, there will be $$$1$$$ element inside ($$$a_1$$$) and $$$1$$$ element outside ($$$a_2$$$), and the answer will be invalid.

In the second test, it is possible to choose the range $$$[2, 2]$$$, and split the array in subarrays $$$(1, 3)$$$ and $$$(4, 4)$$$, in subarray $$$(1, 3)$$$ there are $$$2$$$ elements inside the range ($$$a_2$$$ and $$$a_3$$$) and $$$1$$$ element outside ($$$a_1$$$), in subarray $$$(4, 4)$$$ there is only $$$1$$$ element ($$$a_4$$$), and it is inside the range.

In the third test, it is possible to choose the range $$$[5, 5]$$$, and split the array in subarrays $$$(1, 4)$$$, $$$(5, 7)$$$ and $$$(8, 11)$$$, in the subarray $$$(1, 4)$$$ there are $$$3$$$ elements inside the range and $$$1$$$ element outside, in the subarray $$$(5, 7)$$$ there are $$$2$$$ elements inside and $$$1$$$ element outside and in the subarray $$$(8, 11)$$$ there are $$$3$$$ elements inside and $$$1$$$ element outside.