Problem B: Blue Chips

N people are playing the following game: Everyone stands in a circle at equal distances from their 2 neighbours and starts with a certain number of blue chips. The game is played in K rounds: In each round, you add up the number of chips that every person within a certain distance (D) from you has, and that is the number of chips that you start the next round with. (Note that you do not consider the number of chips you currently have in this computation).

After the K rounds, each player will get a score based on the number of blue chips they have. Player i's score is the number of blue chips that Player i has mod N. For example, if you have 16 blue chips, and N=7, then your score would be 2. The winner is the player (or players) with the smallest score.

Note that when you are computing the distance between you and another person, you simply need to count the number of people between you and them. This means that your two neighbours are at distance 1 from you, the people beside them are at distance 2 from you, etc. You will always take the shortest way around the circle when computing the distance.

Input Format

The first line of the input contains an integer T (1 ≤ T ≤ 10), the number of test cases. Then follow T test cases, each on two lines. The first line contains 3 integers: N (2 ≤ N ≤ 50), K (1 ≤ K ≤ 109) and D (1 ≤ 2*D ≤ N). The second line contains N integers Xi (1 ≤ Xi ≤ 1,000), the starting number of blue chips each player is holding, in clockwise order around the circle.

Output Format

For each test case, output two lines: The first line should contain the score of the winner(s). The second line contains a list of all winners separated by a space in increasing order. The first person listed in the input is player 1, the second person in the input is player 2, and so on. The last person in the input is person N. Player 1 and player N are neighbours.

Sample Input

3 3 1
1 2 2

Sample Output

2 3

Darcy Best
ACPC 2013