Moving Day

Time limit1sMemory limit128 MB

Summary

Given n people each moving from one address to another on a single street, find the lexicographically smallest order of moves so every destination is vacant in time.

Level: Medium5 of 10
Topics: Graph, Topological sort, Greedy
Solved: No attempts yet

Problem

Every year on July 1st, the residents of Quebec experience Moving Day. Most apartment leases begin and end on this day, so it is a popular time to move. The streets fill with moving trucks and anxious tenants packing and unpacking their belongings, waiting for a truck to become free or for a previous tenant to vacate an apartment. It is a busy but profitable time for moving companies.

You will write a program to help the residents of a small town plan the order in which they should move. Only one truck is available, so everyone who is moving must share it. Therefore the people must move one at a time. A person cannot move into a new house until the former tenant has moved out. Each person moves directly from their old house to their new house; a person may not move temporarily into another vacant house while waiting for their new house to be vacated.

You may assume that no two people are moving into the same house. You may assume that no two people are moving out of the same house. You may also assume that every house someone is moving into is either already vacant or is being vacated on Moving Day.

Input

The first line contains the number $n$ ( $1 \le n \le 100$ ) of people who are moving. Each of the following $n$ lines contains a person's name, followed by the address they are moving from and the address they are moving to. Because the town has only one street (Main St.), each address is a single integer between $1$ and $100$ inclusive. No name is longer than 100 characters, and names contain only alphanumeric characters.

Output

Print the names of the people, one per line, in the order in which they should move. If several valid orders exist, print the lexicographically smallest one: compare the sequences of names using standard string ordering and print the smallest such sequence. Equivalently, at each step move the person with the smallest name among those who can move right now. If there is no order that guarantees each person's new house is vacant by the time they move into it, print only the word "Impossible".

Examples3

Example 1

Input

3
Pierre 51 43
Guy 28 83
Marie 43 28

Expected output

Guy
Marie
Pierre

Example 2
Input
```
2
Alice 1 2
Bob 2 1
```
Expected output
```
Impossible
```
Example 3
Input
```
2
Zoe 1 2
Amy 3 4
```
Expected output
```
Amy
Zoe
```