Helianthuswolf Co., Ltd. is a multinational "Intestnet" company. Its revenue from global markets grew year by year. Helianthuswolf's culture is the most important key to its success.
What is Helianthuswolf's culture? Helianthuswolf values innovation, passion, quality, collaboration, and diversity. As Helianthuswolf has grown into a giant successful multinational company and has a huge growing number of global offices, now it values diversity the most.
Anyway, the giant ship is not always smooth sailing. Helianthuswolf has recently suffered a financial crisis. It decides to lay off to survive the crisis. Each department has to lay off a certain number of programmers. To combat age discrimination and to respect the diversity culture, Helianthuswolf decides to keep age diversity after the layoff.
But the recruiters in Helianthuswolf are exaggerated and stereotyped slightly. They need a quantifiable formula to measure diversity. After reading the math book, they think variance is the best measure of diversity. So they want to maximize the variance of the ages of the remaining programmers after the layoff.
In probability theory and statistics, variance is the expectation of the squared deviation of a random variable from its mean. The variance of \(\{x_1, x_2, ..., x_k \}\) is \(\frac{1}{k}\sum\limits_{i=1}^{k}{(x_i - \frac{1}{k}\sum\limits_{j=1}^{k}{x_j})^2}\).
Please help the recruiters to write a program to decide which programmers will be laid off.
There are multiple test cases. The first line of input contains an integer \(T\), indicating the number of test cases. For each test case:
The first line contains two integers \(n\) and \(m\) (\(1 \le n \le 10^5\), \(0\le m < n\)), indicating the number of programmers in that team and the number of programmers the company will lay off.
The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\) (\(0 \le a_i \le 10^4\)), indicating the age of each programmer.
It is guaranteed that the sum of \(n\) over all the cases is less than \(2 \times 10^6\).
For each test case, output \(n - m\) integers in one line in increasing order. The \(n - m\) integers are the indices of the remaining programmers. If there are multiple solutions maximizing the variance, please choose the lexicographically smallest one. DO NOT output extra spaces at the end of each line.
Sequence \(\{x_1, x_2, \dots, x_p\}\) is lexicographically smaller than sequence \(\{y_1, y_2, \dots, y_q\}\), if either \(p < q\) and \(x_i=y_i\) for all \(1 \le i \le p\), or there exists an integer \(r\) (\(r < p\), \(r < q\)) such that \(x_i = y_i\) for all \(1 \le i \le r\) and \(x_{r+1} < y_{r+1}\).
9 3 2 34 35 36 4 2 20 35 41 74 5 2 40 30 50 20 10 5 2 50 40 30 20 10 5 2 10 20 30 40 50 5 3 30 40 20 10 50 5 4 10 20 30 40 50 5 1 30 50 40 20 10 5 0 30 50 40 20 10
1 1 4 1 3 5 1 2 5 1 2 5 4 5 1 2 3 4 5 1 2 3 4 5
In the first case, laying any two programmers off does not change variance, so we have three candidate answers "1", "2" and "3". Among the three answers, "1" has the smallest lexicographical order. So we output "1" (without quotes).
In the second case, laying a 35-year-old (the 2nd one) and a 41-year-old (the 3rd one) programmer off maximises the variance. As "1 4" is lexicographically smaller than "4 1", we output "1 4" (without quotes).
In the third case, we have 12 candidate answers "1 3 5", "1 5 3", "3 1 5", "3 5 1", "5 1 3", "5 3 1", "3 4 5", "3 5 4", "4 3 5", "4 5 3", "5 3 4" and "5 4 3". As "1 3 5" is the lexicographically smallest one, we output "1 3 5" (without quotes).