Problem A
Austan Atlantshafs
Languages
en
is
Many cities and other institutions have a tendency to raise statues of various kinds to garner attention. In this context larger statues are of course preferable, as a larger statue garners more attention. It is even better when the statue is the largest in a large area around where it is raised. Each such institution wants to advertise its statue as “the largest statue in X” where X is the largest named area which makes the statement true. For example if a statue were the largest in all of Europe, it would be a far better advertisement to claim it is the largest in all of Europe rather than it being the largest in Iceland, even though that would also be true if the statue were located in Iceland. Note that if, for example, Germany and France had equally large largest statues, neither of them would be the largest in all of Europe.
Input
The first line of input contains a single integer $n$, the number of named areas, satisfying $1 \leq n \leq 100\, 000$. Next there are $n$ lines, each describing one named area. The $i$-th line contains a string $s_i$, a string $t_i$ and a positive integer $x_i$, separated by spaces. $s_i$ gives the name of the $i$-th area and $t_i$ gives the name of the area the $i$-th area is contained in. $t_i$ is always one one of the areas named in the input. $x_i$ then gives the height of the statue raised in the $i$-th area, where $1 \leq x_i \leq 10^9$ if there is a statue in that area and $x_i = -1$ otherwise. If the area contains smaller areas $x_i = -1$ will hold, but $x_i > 0$ otherwise. No two different areas have the same name.
Each string in the input has length at most $20$ and contains only lowercase English letters. The total length of all strings in the input is at most $10^6$.
The first area is always jord, which is given to contain itself. No other area contains itself, directly or indirectly.
Output
For each area with a statue, print the name of the largest area such that the statue is the largest statue in that area. An area is considered larger than another if it contains the other area. The names should be printed on separate lines, and given in the same order as the input.
| Sample Input 1 | Sample Output 1 |
|---|---|
17 jord jord -1 evropa jord -1 asia jord -1 amerika jord -1 afrika jord -1 eyjaalfa jord -1 thyskaland evropa 100 frakkland evropa 80 kina asia 130 indland asia 70 norduramerika amerika -1 suduramerika amerika -1 kalifornia norduramerika 110 kanada norduramerika 90 brasilia suduramerika 150 sudurafrika afrika 140 astralia eyjaalfa 200 |
evropa frakkland asia indland norduramerika kanada amerika afrika jord |
