#!/usr/bin/perl -w

package Tnode;

sub new {
   my( $class, $word, $count ) = @_;
   my $self = {};
   $self->{word}  = $word;
   $self->{count} = $count;
   $self->{left}  = undef;
   $self->{right} = undef;

   return bless $self, $class;
}

package main;

die unless @ARGV;

my $root = undef;

while(<>) {
   chomp;
   $word = $_;
   $root = tree( $root, $word );
}

treeprint( $root );

sub tree {
   my( $node, $word ) = @_;

   if( ! $node ) {
      $node = Tnode->new( $word, 1 );
      $node->{left} = undef;
      $node->{right} = undef;
   } elsif( $node->{word} eq $word ) {
      $node->{count}++;
   } elsif( $word lt $node->{word} ) {
      $node->{left} = tree( $node->{left}, $word );
   } else {
      $node->{right} = tree( $node->{right}, $word );
   }

   return $node;
}

sub treeprint {
   my( $root ) = shift;

   if( $root ) {
      treeprint( $root->{left} );
      printf( "%4d %s\n", $root->{count}, $root->{word} );
      treeprint( $root->{right} );
   }
}