Problem hidden
This problem was hidden by Editorial Board member probably because it has incorrect language version or invalid test data, or description of the problem is not clear.

EIUSTUDE - Mission impossible

Beo receives a new task from the fastidious village chief. He was given a list of the names of beautiful single girls in the village, but the list was arranged randomly so finding a girl in the list was very inconvenient. Therefore, Beo must sort the list according to the followings:

  • List sorted in alphabetical order.
  • The list is sorted in alphabetical order.
  • The list is sorted by first name then by last name and middle name.

As Beo's friend, help him to  finish this task as soon as possible, so you can find out your future girlfriend.

Input

+ The first line is an integer N (1 <= N <= 10 ^ 5) is the number of names in the list.

+ The ith line of the following N lines is the full name of the criminals (Example: nguyen a, tran thanh B). For simplicity, the first name has 2-5 words, including only the letters a-z, the words separated by spaces, and the last word is the first name, the first word is a last name.

Output

+Output the list of names in the request order.

Example

Input:
5
nguyen thanh tu
nguyen thanh binh
nguyen tan
tran trong tan
tran trong binh

Output:
nguyen thanh binh
tran trong binh
nguyen tan
tran trong tan
nguyen thanh tu

Added by:Ha Minh Ngoc
Date:2015-02-05
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:CSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG FSHARP GO JAVA JS-MONKEY NODEJS PHP PYTHON PYPY PYTHON3 RUBY SQLITE SWIFT VB.NET
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.