SP238 HOLIDAY2 - Getting Rid of the Holidays (Act II)

As King Johnny's temporary indisposition lengthens from days to weeks, and you still hold the office of Regent of Byteland, you begin to feel that acting king is not all that much fun. You encounter various absurdly weird problems. For instance, you find that contrary to your expectations the recent removal of holidays brought about a decrease in the efficiency of the kingdom's workforce. There appears to be only one rational explanation for all this. It seems that although every holiday occurs every a fixed number of days, the periods between consecutive holidays are long and very irregular. And it is the lack of regularity that is the root of the problem. So, you decide it is time to tackle the problem once again, and solve it properly this time. Your main purpose is to establish an r-day working rhythm (for some integer r). Workers will work for (r-1) days, have a single day off, work for another (r-1) days, and so on. The rhythm must be arranged in such a way that holidays only ever occur on the day off work. Choose exactly k of the n holidays to remove in such a way as to be able to establish a working rhythm of the maximum possible length r. **Solve the problem in at most 4kB of source code.**

The first line of input contains a single integer t

For each test case, output one line containing an increasing sequence of exactly k integers - the numbers of the holidays to be removed (holidays are numbered in the input order from 1 to n).