Water Slides

Statement

This problem takes place on a private island in the sea.

Around the circumference of the island there are \(n\) points where it’s possible to build infrastructure. These points are numbered from \(0\) to \(n-1\) in clockwise order.

The \(n\) points have mutually distinct altitudes. These are given: point \(i\) is \(H[i]\) meters above the sea.

The owner of the island wants to build a water park on the island. The main attraction should be a set of \(k\) water slides. Each water slide will take you on a ride across the island and in the end it will drop you into the sea.

More formally, the water slides should satisfy the following requirements:

Each water slide must begin in one of the \(n\) points and end in another of those \(n\) points.
Obviously, each water slide must go downhill. To ensure this, the height of its start must be greater than the height of its end.
When looking at the island from above, each water slide must be a smooth curve that is (except for its endpoints) strictly on the island.
For safety reasons, water slides can never cross each other. I.e., when looking at the island from above, the curves that represent the water slides must all be mutually disjoint, including their endpoints.

Determine whether such a set of slides can be built. If yes, also find the best possible set of slides. For this purpose, the quality of a slide is the height difference between its endpoints, and the quality of a set of slides is the sum of their individual qualities.

You may assume that the park’s construction crew is very capable: they will take care of all the necessary landscaping and they will be able to build the slides as long as you choose the starts and ends of all slides so that:

each slide starts higher than it ends, and
the endpoints are chosen in such a way that on a map of the island it is possible to draw the slides as disjoint smooth curves.

Input format

The first line of each input file contains the number \(t\) of test cases. The specified number of test cases follows, one after another.

Each test case consists of two lines. The first line has the integers \(n\) and \(k\). The second line has the heights of the \(n\) points: the integers \(H[0], \dots, H[n-1]\).

In each test case:

\(2 \leq n\)
\(1 \leq k \leq n/2\)
for each \(i\): \(0\leq H[i]\leq 10^9\)
the values \(H[i]\) are mutually distinct.

Output format

For each test case, in order, output \(k\) lines with its solution.

If there is no way of building the slides according to the rules, each of the \(k\) lines should have the form “\(-1\) \(-1\)”.

Otherwise, pick and output one optimal solution. For each slide in the optimal solution, output one line of the form “\(a_i\) \(b_i\)”, where \(a_i\) is the number of the point where the slide begins and \(b_i\) the point where it ends.

Subproblem W1 (11 points, public)

Input file: W1.in

Constraints: \(t=10\), \(n\leq 20\), \(k=1\).

Subproblem W2 (22 points, public)

Input file: W2.in

Constraints: \(t=20\), \(n\leq 10\).

Subproblem W3 (44 points, secret)

Input file: W3.in

Constraints: \(t=100\), \(n\leq 100\).

For this subproblem you can get a partial score of 10 points for correctly identifying solvable inputs, even if your collection of slides is invalid. More precisely, if you want this partial score, for unsolvable inputs you must still output the \(-1\)s, while for solvable inputs you may print any output with \(k\) lines, each containing two integers from the range \([0,n-1]\).

Subproblem W4 (23 points, secret)

Input file: W4.in

Constraints: \(t=5\), \(n\leq 100\,000\).

Example

input

2
8 1
50 20 90 30 40 10 60 80
8 3
50 20 90 30 40 10 60 80

output

Notes about the first test case:

This is the only optimal solution.
Remember that order matters: “5 2” is not a valid answer, as that represents a slide from point 5 to point 2.

Notes about the second test case:

Other optimal solutions exist, and any of those would also be accepted.
If we had a 7 → 4 slide instead of the 7 → 1 slide, the set of slides would still be valid, i.e., we could build those three slides according to the rules. However, this new set of slides would no longer be optimal.
It is not allowed to build both a 2 → 5 slide and a 6 → 3 slide because it is not possible to build the two slides without having an intersection.