Galcatic Gulls
A long, long time ago, in a galaxy far, far away (no, it's not where you're thinking, it's a different part of the universe), a planet of sentient seagulls fights in outer space over the most coveted resource: chips.
Seagulls are very greedy animals. Because they are so greedy, they have exhausted their planet's entire supply of chips. Now, the various seagull nations have set their beady eyes on the stars. They have built spaceships capable of bringing home chips from the chip asteroids in their solar system.
The United Gull Nations (UGN) is unsuccessfully attempting to create a system where the seagull nations can share the space chips equitably. The UGN scans for chips in outer space, and when it finds a chip asteroid, it alerts every seagull nation simultaneously.
Unfortunately, this system results in every nearby seagull spaceship rushing towards newly found chip asteroids immediately. Seagulls are, after all, very greedy animals.
The most recently announced asteroid can be stored in three spaceships. That means that only the first three seagulls to reach this asteroid will get any chips. There will be no chips left behind for any other seagulls.
Based on the current distances and speeds of the seagulls, which three seagulls can reach the asteroid first, and in what order do they reach it?
Note: The first three seagulls to reach the asteroid will never arrive at the same time as each other, nor will they arrive at the same time as any other seagull. One seagull is strictly the first, another is strictly the second, and another is strictly the third.
Input
The input consists of several lines.
The first line contains an integer \(3 \leq n \leq 1000\) representing the amount of seagulls.
Then, there are \(n\) lines. Each line has:
- A string \(w_i\) (\(1 \leq |w| \leq 10\)) consisting only of lowercase English characters representing the \(i\)th seagull's name
- An integer \(1 \leq d_i \leq 500\) representing the \(i\)th seagull's distance from the asteroid in units
- An integer \(1 \leq s_i \leq 500\) representing the \(i\)th seagull's speed in units per second
All seagulls are currently flying directly towards the asteroid, and their speeds are constant. Acceleration, et cetera is not a part of this exercise.
Output
The program must output three lines. Each line contains the name of a seagull;
- The first line contains the name of the first seagull to reach the asteroid
- The second line contains the name of the second seagull to reach the asteroid
- The third line contains the name of the third seagull to reach the asteroid
Examples
Example 1
Input:
5
scuttle 40 1
irving 30 1
garvey 45 1
jonathan 50 1
numenia 52 1
Output:
irving
scuttle
garvey
Example 2
3
scuttle 10 52
jonathan 13 55
garvey 9 41
scuttle
garvey
jonathan
Comments