Fluttershy's Ducks

Fluttershy has many ducks. So many, in fact, that she's lost track of them all!

To keep her ducks in a row, Fluttershy has given each of them a first and last name.

Sort these ducks by their last name. Ducks with the same last name should be ordered by their first name.

Input

The first line will contain one integer, $1 \le N \le 10^5$.

This will be followed by $N$ lines. Each of these lines contains two space-separated words: the first name and last name of a duck, respectively.

All names are at most 10 characters in length and consist of lowercase ASCII letters.

Output

Output the names of the sorted ducks, one duck per line.

Subtasks

• Subtask 1 (30%): $1 \le N \le 100$ and all first names are equal to trevor.
• Subtask 2 (30%): $1 \le N \le 100$ and all last names are distinct.
• Subtask 3 (40%): No restrictions.