You'll be given a list of students, and you'll need to sort it using selection sort. We want to sort the students according to graduation year (soonest first), and for students with the same graduation year, alphabetically by first name (and if there are any students with the same first name and graduation year, ties should be broken by last name). However, rather than just printing the final sorted list, you'll print the partially sorted list after each pass (equivalently, after each selection of the smallest element).

Input Format

The first line of the input consists of an integer, n, indicating the number of words you'll need to sort. The next n lines will each consist of student data wtih space-separated first name, last name, and graduation year, in that order. The input will terminate with a blank line. For example:

6 priya murali 2018 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 diane wang 2014 

Constraints

You can assume n is a non-negative integer. You can further assume the list contains no students with the same first name, last name, and graduation year.

Output Format

You will be printing the partially sorted list n - 1 times (the last time will be entirely sorted). Each student should appear on a new line without terminating whitespace, space separated in the same format it was provided in the input, and each partially sorted list should be followed by a blank line to indicate where it ends and the next one begins. For example:

diane wang 2014 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 stephanie liu 2018 stephanie rothermel 2018 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 stephanie liu 2018 stephanie rothermel 2018 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie rothermel 2018 stephanie liu 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie liu 2018 stephanie rothermel 2018 

Sample Input 0

6 priya murali 2018 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 diane wang 2014 

Sample Output 0

diane wang 2014 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 stephanie liu 2018 stephanie rothermel 2018 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 stephanie liu 2018 stephanie rothermel 2018 priya murali 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie rothermel 2018 stephanie liu 2018 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie liu 2018 stephanie rothermel 2018