James has a student roster list where each row looks like Student Name, Graduation Year. He believes the only way to sort this list is to randomize the rows and manually check if its sorted. Prove him wrong by implementing 3 faster ways to sort Jamess student roster. The student roster must be sorted 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). Rather than just printing the final sorted list, youll print the partially sorted list after each pass.

Input

The first line contains an integer n, 0 n 10, denoting the number of students you will need to sort.

The next line n lines will each consist of student data with space-separated first name, last name, and graduation year, in that order.

The input will terminate with a blank line.

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

You will be printing the partially sorted list as many times as necessary based on the sorting algorithm you are implementing. Look at the hacker rank challenge for sample input and output for the different algorithms.

INSERTION SORT

MERGE SORT

Sample Input 0

8 danielle rothermel 2015 sarah shatan-pardo 2017 david shatan-pardo 2015 alisa nguyen 2015 todd hirsch 2017 lina kroehling 2015 jess geiger 2014 anita garcia 2017 

Sample Output 0

danielle rothermel 2015 sarah shatan-pardo 2017 david shatan-pardo 2015 alisa nguyen 2015 todd hirsch 2017 lina kroehling 2015 jess geiger 2014 anita garcia 2017 danielle rothermel 2015 sarah shatan-pardo 2017 alisa nguyen 2015 david shatan-pardo 2015 todd hirsch 2017 lina kroehling 2015 jess geiger 2014 anita garcia 2017 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 sarah shatan-pardo 2017 todd hirsch 2017 lina kroehling 2015 jess geiger 2014 anita garcia 2017 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 sarah shatan-pardo 2017 lina kroehling 2015 todd hirsch 2017 jess geiger 2014 anita garcia 2017 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 sarah shatan-pardo 2017 lina kroehling 2015 todd hirsch 2017 jess geiger 2014 anita garcia 2017 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 sarah shatan-pardo 2017 jess geiger 2014 lina kroehling 2015 anita garcia 2017 todd hirsch 2017 jess geiger 2014 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 lina kroehling 2015 anita garcia 2017 sarah shatan-pardo 2017 todd hirsch 2017

QUICK SORT

Sample Input 0

8 danielle rothermel 2015 sarah shatan-pardo 2017 david shatan-pardo 2015 alisa nguyen 2015 todd hirsch 2017 lina kroehling 2015 jess geiger 2014 anita garcia 2017 

Sample Output 0

jess geiger 2014 alisa nguyen 2015 david shatan-pardo 2015 anita garcia 2017 todd hirsch 2017 lina kroehling 2015 danielle rothermel 2015 sarah shatan-pardo 2017 jess geiger 2014 alisa nguyen 2015 david shatan-pardo 2015 anita garcia 2017 sarah shatan-pardo 2017 lina kroehling 2015 danielle rothermel 2015 todd hirsch 2017 jess geiger 2014 alisa nguyen 2015 david shatan-pardo 2015 anita garcia 2017 danielle rothermel 2015 lina kroehling 2015 sarah shatan-pardo 2017 todd hirsch 2017 jess geiger 2014 alisa nguyen 2015 david shatan-pardo 2015 lina kroehling 2015 danielle rothermel 2015 anita garcia 2017 sarah shatan-pardo 2017 todd hirsch 2017 jess geiger 2014 alisa nguyen 2015 david shatan-pardo 2015 danielle rothermel 2015 lina kroehling 2015 anita garcia 2017 sarah shatan-pardo 2017 todd hirsch 2017 jess geiger 2014 alisa nguyen 2015 danielle rothermel 2015 david shatan-pardo 2015 lina kroehling 2015 anita garcia 2017 sarah shatan-pardo 2017 todd hirsch 2017

Sample Input 0 priya murali 2018 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 diane wang 2014 Sample Output 0 priya murali 2018 stephanie rothermel 2018 lilly wang 2016 stephanie liu 2018 annika fusco 2016 diane wang 2014 lilly wang 2016 priya murali 2018 stephanie rothermel 2018 stephanie liu 2018 annika fusco 2016 diane wang 2014 lilly wang 2016 priya murali 2018 stephanie liu 2018 stephanie rothermel 2018 annika fusco 2016 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie liu 2018 stephanie rothermel 2018 diane wang 2014 diane wang 2014 annika fusco 2016 lilly wang 2016 priya murali 2018 stephanie liu 2018 stephanie rothermel 2018