URI Online Judge | 2177

Rio 2016

By Marianne Linhares, Universidade Federal de Campina Grande Brazil

Timelimit: 1

Maria loves sports and she is very excited about the Olympic Games Rio 2016. She was so excited that se bought a lot of tickets for the games, but unfortunately due to the distance between her house and the competition's arenas, that can be very large, she may not be able to watch all the games.

Maria knows you love programming challenges as much as she loves sports, so she asked you to make a program that given the position of the arenas of each game and how much time is left until the match begins, tells which games she will be able to watch if she leaves right now from her current position and go to the arena (she has to get there before the game starts).

Maria is at a certain position (x, y) and moves with velocity of 1 meter per minute (despite of the excitement Maria walks slowly so she can pass by the maximum number of pokestops), the distance of the locations, also in meters, is the Euclidian Distance between the positions, and the time left to the beginning of the game is also in minutes.

Input

The first line of the input consists of Maria's position, x and y (0 ≤ x, y ≤ 1000), and the number n (1 ≤ n ≤ 10⁶) that represents the number of tickets Maria bought.

The next n lines consits of 3 number, xi, yi, ti, respectly the position x of game i, the position y of game i, and the time left to the beginning of the game i. (0 ≤ xi, yi ≤ 1000 e 1 ≤ ti ≤ 1000000).

Output

The output is just one line that contains the sorted indexes of the games Maria will be able to watch. If Maria will not be able to watch any game just print "-1" (without the quotation marks)

 Input Samples Output Samples 0 0 3 0 1 1 1 0 2 0 1 2 2 3
 0 0 3 4 5 10 2 3 3 10 10 20 1 3