Canadian Computing Competition: 2008 Stage 2, Day 1, Problem 1

Every year on July 1st, the residents of Quebec experience Moving Day. It is customary for most apartment leases to begin and end on this day, making it a popular time for people to move. The streets are filled with moving trucks and anxious tenants packing and unpacking their belongings, waiting for their truck to become available, or waiting for a previous tenant to vacate their 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 all of the people who are moving must share it. Therefore, the people must move one at a time. A person cannot move into a new house before 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 each house to which someone is moving is either vacant or being vacated on Moving Day.

Input Specification

The first line of input contains the number ~n~ ~(1 \le n \le 100)~ of people who are moving. Each of the following ~n~ lines of input contains a person's name followed by the address that the person is moving from and the address that the person is moving to. Because there is only one street in the town (called Main St.), each address is just a number between ~1~ and ~100~, inclusive. You can assume that no name will be longer than ~100~ characters, and that names contain only alphanumeric characters.

Output Specification

The program should print the names of the people who are moving in the order that they should move. If it is not possible to find an order that ensures that each person's new house is vacant by the time the person moves to it, the program should print only the word Impossible. If there are several different orders in which the people could move, any valid order is acceptable.

Sample Input

3
Pierre 51 43
Guy 28 83
Marie 43 28

Sample Output

Guy
Marie
Pierre