use strict;
use integer;
#use warnings;

##########
sub isSubsetOf (\@\%) {
    my ($subref,$superref)=@_;
    for my $item (@$subref) {
    return 0 unless defined $$superref{$item};
    }
    return 1;
}

##########
sub joinRows (\@\@) {
    my ($aref,$bref)=@_;
    return undef unless $#$aref==$#$bref and $$aref[$#$aref] lt $$bref[$#$aref];
    for(my $index=0; $index<$#$aref; $index++) {
    return undef unless $$aref[$index] eq $$bref[$index];
    }
    my @aub=@$aref;  $aub[$#$aref+1]=$$bref[$#$aref];
    return \@aub;
}

##########
sub readData {
    my %rows=();
    my %items=();
    my $rowCount=0;
    while(<STDIN>) {
    chomp;
    my @row=split(",", $_);
    $rows{join(" ", @row)}++;
    for my $item (@row) { $items{$item}++; }
    $rowCount++;
    }
    return (\%rows, \%items, $rowCount);
}

##########
sub generateCandidates (\@) {
    my ($itemsetsref)=@_;
    my %candidates=();

    return unless defined @$itemsetsref;

    for(my $i=0; $i<$#$itemsetsref; $i++) {
    my @a=split(" ", $$itemsetsref[$i]);
    for(my $j=$i+1; $j<=$#$itemsetsref; $j++) {
        my @b=split(" ", $$itemsetsref[$j]);
        my $aubref=joinRows(@a, @b);
        if(defined $aubref) {
        $candidates{join(" ", @$aubref)}=0;
        } else {
        $j=$#$itemsetsref+1;
        }
    }
    delete $$itemsetsref[$i];
    }
    return \%candidates;
}

##########
sub frequentSets (\%\%$$) {
    my ($rowsref, $itemsref, $rowCount, $minSupp)=@_;

    for my $item (keys %$itemsref) {
      if($$itemsref{$item}>=$minSupp) {
        print "$$itemsref{$item} $item\n";
      } else {
        delete $$itemsref{$item};
      }
    }
    my @survivors=sort keys %$itemsref;
    %$itemsref =();
    undef %$itemsref;

    my $candidatesref=generateCandidates(@survivors);

    while(scalar(keys %$candidatesref)>0) {
    @survivors=();
    for my $row (keys %$rowsref) {
        my %keys=();
        for my $item (split(" ", $row)) { $keys{$item}=1; }
        for my $candidate (keys %$candidatesref) {
        my @c=split(" ", $candidate);
        $$candidatesref{$candidate}+=$$rowsref{$row} if isSubsetOf(@c, %keys);
        }
    }
    for my $candidate (keys %$candidatesref) {
        if($$candidatesref{$candidate}>=$minSupp) {
          print "$$candidatesref{$candidate} $candidate\n";
        } else {
        delete $$candidatesref{$candidate};
        }
    }
    @survivors=sort keys %$candidatesref;
    %$candidatesref = ();
    $candidatesref=generateCandidates(@survivors);
    }
    return;
}

######################
# The User Interface #
######################
my $minSupp = $ARGV[0];
my ($rowsref,$itemsref,$rowCount)=readData();
frequentSets(%$rowsref,%$itemsref,$rowCount, $minSupp);
exit;
