Sort an array of student records by their names using merge-sort algorithm.

Input

Input begins with n (1 ≤ n ≤ 2²⁰) of number student records. The following n lines has a student record per line. A student record of a student has a unique register number (one alphanumeric word and 3 <= length of the word <= 10), his/her name (one alphabetic word without any spaces and 1 <= length of the name <= 20) and his/her CGPA with the precision up to two digits after decimal point (00.00 <= CGPA <= 10.00). The three fields of a record are separated by spaces.

Output

Print the sorted array with one student record in each new line in ascending order of student’s name. In case of more than one record has a common name, the relative order of the records need to be maintained (i.e., sorting has to be “stable”).

Example

Input:
10
CS003 Vinay 10.00
CS005 Mouli 9.94
CS010 Gautham 9.94
CS020 Sneha 9.94
CS200 Mohit 9.93
CS012 Aarti 9.90
CS006 Darshan 9.88
CS002 Adithya 9.78
CS050 Karthik 9.71
CS001 Adithya 9.58

Output:
CS012 Aarti 9.90
CS002 Adithya 9.78
CS001 Adithya 9.58
CS006 Darshan 9.88
CS010 Gautham 9.94
CS050 Karthik 9.71
CS200 Mohit 9.93
CS005 Mouli 9.94
CS020 Sneha 9.94
CS003 Vinay 10.00