2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8

Horse Racing

Finally, that long-awaited day has come, and you can again watch horse races on the Jydyr plain.

n horses will participate in the races. Each knight is assigned the value ai - the horse's strength. Among them there are k horses of the Karabakh breed. Karabakh horses have one peculiarity. During the arrival, their strength is doubled. But you do not know which horses belong to this breed, that is, each of the horses has a chance to be Karabakh, but there are only k of them.

The strongest horse wins the race. Identify the horses that are most likely to win.

Note: if there are several strongest horses in a race, then everyone has a chance to win.


The first line contains one integer t - the number of test cases.

Then, in each of the following t tests, the first line contains two numbers n and k, and the second line contains n integers ai.

ai denotes the strength of the knight in its normal state. The strength of the Karabakh horses doubles during the race.


Print in ascending order the numbers of the horses that have the probability to win.


  • 1t100
  • 1n105, sum of all n in all tests: ∑n ≤ 105
  • 0kn
  • 1ai109


This problem consists of 3 subtasks:

0Example0 points
1k = 013 points
2n1000, ∑n ≤ 100033 points
3No additional restrictions54 points
Time limit 1 second
Memory limit 256 MiB
Input example #1
2 1
3 5
3 1
2 3 6
Output example #1
1 2
2 3
Author Rashad Mammadov
Source 2021 Azerbaijan, Republic Informatics Olympiad, Semifinal, March 8