Sort an array of student records by their register numbers using Quick 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 register number.

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:
CS001 Adithya 9.58
CS002 Adithya 9.78
CS003 Vinay 10.00
CS005 Mouli 9.94
CS006 Darshan 9.88
CS010 Gautham 9.94
CS012 Aarti 9.90
CS020 Sneha 9.94
CS050 Karthik 9.71
CS200 Mohit 9.93