import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Scanner;

public class InsertionSort{

    public static void  main(String[] args){

        LinkedList<String> list=new LinkedList<>();
        Scanner sc=new Scanner(System.in);

        while ( sc.hasNext() ){
            sortedInsert(sc.next() ,list);
        }

        System.out.println("Sorted:");

        ListIterator<String> iterator=list.listIterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }

    static void sortedInsert(String input, LinkedList<String> list){
        ListIterator<String> iterator=list.listIterator();

        while (iterator.hasNext() ){

            String element=iterator.next();

            if (element.compareTo(input) >0){
                iterator.previous();
                iterator.add(input);
                return;
            }
        }
        iterator.add(input);
    }

}


//@keywords: insertion sort, sort, linked list, week 10