Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

Fluttershy's Ducks

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 100 megabytes
Time limit: 1.5 seconds

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.
  • Sample Input 1

    3
    trevor henry
    trevor mallard
    trevor chinn
    

    Sample Output 1

    trevor chinn
    trevor henry
    trevor mallard
    
  • Sample Input 2

    5
    tom levy
    logan glasson
    tom bombadil
    tony sun
    tom morrison
    

    Sample Output 2

    tom bombadil
    logan glasson
    tom levy
    tom morrison
    tony sun
    
  • Sample Input 3

    6
    rainbow junior
    bon bon
    flutters junior
    discord junior
    flutters senior
    princess celestia
    

    Sample Output 3

    bon bon
    princess celestia
    discord junior
    flutters junior
    rainbow junior
    flutters senior