Arrange Books with Distinct Adjacent Genres

You are given a collection of books. Each book is described by its name and genre. Your task is to rearrange the books so that no two adjacent books belong to the same genre.

If it is possible to obtain such an arrangement, print the arranged book names in order (separated by a single space). Otherwise, print impossible.

Note: When multiple valid arrangements exist, your solution must follow the deterministic strategy defined below. For each genre, sort the book names in lexicographical order. Then, use a greedy algorithm that always picks the genre with the highest remaining count; if the top candidate has the same genre as the last placed book, choose the next candidate (if available). If no valid rearrangement is possible, output impossible.

The input is given from standard input and the output should be printed to standard output.

inputFormat

The first line contains an integer n — the number of books.

Each of the following n lines contains two strings separated by a space: the name of the book and its genre.

All book names and genres consist of alphanumeric characters without spaces.

outputFormat

If a valid arrangement exists, print a single line containing the arranged book names separated by a single space.

If no valid arrangement exists, print a single line containing the word impossible.

## sample

3
HarryPotter Fantasy
Dune ScienceFiction
Eragon Fantasy

Eragon Dune HarryPotter

</p>