use strict;
use warnings;

my $digest = bless {root => {}, maxLevel => 3};

$digest->add ($_) while <DATA>;
$digest->mergeTails ();
$digest->print ();

sub add {
    my ($self, $line, $level, $context) = @_;
    $level ||= 1;
    $context ||= $self->{root};
    
    if ($level == $self->{maxLevel} or $line !~ s/(\S*?)\s*\W\s+//) {
        push @{$context->{tails}}, $line;
        return;
    }
    
    my $prefix = $1;
    
    $context->{$prefix} ||= {};
    $context = $context->{$prefix};
    $self->add ($line, 1 + $level, $context);
}


sub mergeTails {
    my ($self, $context) = @_;
    $context ||= $self->{root};

    unless (exists $context->{tails}) {
        $self->mergeTails ($context->{$_}) for keys %$context;
        return;
    }
    
    my @tails = sort {length $a <=> length $b} @{$context->{tails}};
    my @groups;
    
    push @{$groups[length $_]}, $_ for @tails;
    @groups = grep {defined $_} @groups;
    
    for my $group (@groups) {
        my $mask = pop @$group;
        my $count = 1;
        
        while (@$group) {
            my $str = pop @$group;
            my $mix = $mask ^ $str;
            my $cpl = "\xff" x length $mix;
            
            $mix =~ tr/\0/\xff/c;
            $mix = $mix ^ $cpl;
            $mask = $mask & $mix;
            ++$count;
        }
        
        $mask =~ tr/\0/*/;
        push @{$context->{digest}}, [$mask, $count];
    }
}


sub print {
    my ($self, $context, $indent) = @_;
    $context ||= $self->{root};
    $indent ||= '';
    
    if (exists $context->{digest}) {
        print "$indent($_->[1]) $_->[0]" for @{$context->{digest}};
        return;
    }
    
    for (sort keys %$context) {
        print "$indent$_\n";
        $self->print ($context->{$_}, $indent . '    ');
    }
}


__DATA__