SP11116 PONY4 - Discord is Cornered

The ponies have finally cornered Discord. His earlier escape attempts didn't help him much. The unicorn ponies have begun casting magic spells at Discord to turn him back into stone. There are N ponies and pony I has a casting rate A\_I. That is, once pony I began casting her magic spell, it would send a bolt of magic at Discord every A\_I seconds, precisely. At time t = 0 seconds, all the ponies began casting their magic. It has now been M seconds since they began casting. Discord is wearing down. He only can survive being hit by K-1 more spells before being turned into stone (so the Kth spell will turn him to stone). Determine which pony has the honor of casting the final blow against Discord. Notes: If multiple ponies send a bolt of magic at the same time, then they hit in order of the smaller rate first. All the ponies are casting different spells, so all the casting rates are distinct. If some ponies cast a bolt of magic after exactly M seconds, that bolt has already hit Discord. He can survive an additional K-1 spells.

The input file will begin with a number T on the first line, indicating the number of test cases in the file. It is followed by 2T lines, which represent the T test cases. Test case i begins with the label "Case #i: " and is followed by space separated N, M, and K for that case. On the next line are N space separated integers representing the rates of pony0, pony1, ..., ponyN-1. ``` T //number of test cases Case #1: N M K//number of ponies, number of seconds since they began casting, the spell which will turn him to stone A_0 A_1 ... A_N-1 ... (etc.) ```

The output contains T lines, one for each test case. For test case i, begin the line with the label "Case #i: ", and then the index of the pony which has dealt the final blow against Discord. ``` Case #1: C_1 //C_1 is the pony which casts the final blow against Discord Case #2: C_2 ... Case #T: C_T ``` Limits ------ ``` Limits: Number of Test cases varies. Depends on the instance size. 1