#!/usr/bin/perl

#    merge_sort.pl
#          
#    Copyright(C) Since 2006 Akira KAKINOHANA All Rights Reserved
#    Author :  Akira KAKINOHANA <kira@kirameister.net>
#    Distributed at : http://softwares.kirameister.net/
#    
#    This program is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation version 3.
#
#    This program is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    For GNU General Public License, see <http://www.gnu.org/licenses/>.


my @table;
my $N = 0;
while(<STDIN>){
    chomp;
    $table[$N] = $_;
    $N++;
  }
&sort(\@table);

foreach $k (@table){
    print "$k\n";
  }

sub sort {
    (my $a) = @_;
    my $num = @$a;
    my $ref = \@a;
    &mergeSort($a);
  }

sub mergeSort {
    (my $a) = @_;

    return if (@$a <= 1);

    my $m = int( @$a / 2 );
    my $n = @$a - $m;

    my @a1;
    my @a2;
    for (my $i=0;$i<$m;$i++){$a1[$i] = $$a[$i]}
    for (my $i=0;$i<$n;$i++){$a2[$i] = $$a[$m+$i]}
    &mergeSort(\@a1);
    &mergeSort(\@a2);
    &merge(\@a1, \@a2, $a);
  }

sub merge {
    ($a1, $a2, $a) = @_;
    $i = 0;
    $j = 0;

    while ($i < @$a1 || $j < @$a2) {
        ($cola1) = split( / /, $$a1[$i]);
        ($cola2) = split( / /, $$a2[$j]);
        if ($j >= @$a2 || ($i<@$a1 && $cola1 < $cola2) ) {
            $$a[$i+$j] = $$a1[$i];
            $i++;
	  }else{
            $$a[$i+$j] = $$a2[$j];
            $j++;
	  }
      }
  }