import java.util.ArrayList;
import java.util.Scanner;

public class MergesortBU
{
	// Notkun: merge(a, aux, lo, mid, hi);
	// Fyrir:  a[lo..mid] er í vaxandi röð
	//         a[mid+1..hi] er í vaxandi röð
	// Eftir:  a[lo..hi] er í vaxandi röð
	private static void merge(String[] a, String[] aux, int lo, int mid, int hi)
	{
		for (int k = lo; k <= hi; k++)
			aux[k] = a[k];

		int i = lo;
		int j = mid+1;

		for (int k = lo; k <= hi; k++)
		{
			// a[lo..k] inniheldur tölurnar úr
			// aux[lo..i-1] og aux[mid+1..j-1]
			// í vaxandi röð
			//
			// aux invariant:
			// | done | todo | done | todo  |
			//  ^      ^    ^        ^     ^
			//  lo     i    mid      j     hi

			if      (i > mid)              a[k] = aux[j++];
			else if (j > hi)               a[k] = aux[i++];
			else if (less(aux[j], aux[i])) a[k] = aux[j++];
			else                           a[k] = aux[i++];
		}
	}

	private static void sort(String[] a)
	{
		int N = a.length;
		String[] aux = new String[N];

		for (int sz = 1; sz < N; sz = sz+sz)
			for (int lo = 0; lo < N-sz; lo += sz+sz)
				merge(a, aux, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
	}

	private static boolean less(String a, String b)
	{
		return a.compareTo(b) < 0;
	}

	public static void main(String[] args)
	{
		ArrayList<String> q = new ArrayList<String>();
		Scanner scan = new Scanner(System.in);

		while (scan.hasNext())
		{
			q.add(scan.nextLine());
		}

		String[] f = q.toArray(new String[0]);

		long start = System.nanoTime();
		sort(f);
		long stop = System.nanoTime();
 
		double duration = (stop-start) / 1000000.0;

		System.out.printf("Sorted %d lines in %.2f ms\n", q.size(), duration);

		for (int i = 0; i < f.length; i++)
			System.out.println(f[i]);
	}
}