Deadpool has waited 1 year 3 weeks 6 days and 14 minutes and finally, Deadpool has found Francis.Deadpool told Fancis to fix his face. But as you know Francis is "pure evil". So Francis gave him a task to make a robot dog for him (Francis). His (Francis) requirements were:
There will be n bones around the dog (in positive xi and yi axis). And it should be able to pick the farthest bone from its (dog’s) position (x,y).
There can be multiple bones in one coordinate. In this case, bone that comes later (in input) will be placed on the last added bone in that coordinate. And robot dog will always choose the topmost bone.
For example, initially there is no bone in position , then Francis adds a bone at this position. So now position contains only one bone . If he adds another bone in the same position then will be placed on . So if is farthest point then robot dog will choose from this position.
Deadpool solved the problem but Francis was not happy with him. Now Francis thinks if this dog can choose the -th farthest point instead of farthest point and picks its topmost bone then he can try to fix Deadpool.
Deadpool thinks he can solve this too but he has some bad guys to kill. So he wants your help.
You may think in which universe does a superhero need help from normal people? Well just remember what Deadpool say –
“I may be super, but I'm no hero.”
Anyway, the point is, he really needs your help. As you are a great programmer and fan of Deadpool you really want to help him right?
You have to write a program for Deadpool that will take the robot dog’s position and positions of n bones, and give the index (1 based) of the bone that the robot dog will pick as output. If there are different coordinate with the same distance he has to choose the one which comes first in input. And if -th farthest point doesn’t exist you have to print “-1” (w/o quotes).
One more thing, you can safely assume that no bone will be on the same coordinate with dog.
First line of input will be (), the number of testcase. First line of every testcase will contain two integer a nd (), position of the robot dog.
Then next line will contain two positive integers , , where (). Then line will contain two positive integers , (),coordinate of -th bone.
For each testcase your output format should be “Case x: y”. (w/o quotes). Where is the test case number and is the index of bone that will be picked by the robot dog if it exists, otherwise “-1” (w/o quotes).
Input | Output |
---|---|
2 0 0 5 2 2 3 3 2 2 3 3 2 1 1 0 0 5 3 2 3 3 2 2 3 3 2 1 1 | Case 1: 3 Case 2: -1 |
Formula for calculating distance between two points: .