#!/usr/bin/perl

use strict;
use warnings;

my %words;
while(<>) {
    chomp;
    $words{ lc $_ } = 1;
    
}

foreach my $word (keys %words) {
    next unless length $word == 9;  # must be 9 chars long
    next unless $word =~/[ai]/;     # must have letter a or i in it
    print "$word " if subwords($word);  #if subwords evaluates to true, print the word
}
print "\n";

sub subwords {
    my $word = shift;
    return 1 if $word eq "a" or $word eq "i";   # base case: we've found a word that ends with a or i.
    for my $index (0..length($word)-1) {        # for each index of $word
        my $subword = $word;                    # clone $word into $subword
        substr($subword, $index, 1, "");        # remove character at $index (e.g. friend becomes frend, etc)
        next unless $words{ $subword};          # check if what remains is a word (in dictionary) if it's not, continue looping.
        next unless subwords( $subword);        # recursion: perform this same step on the subword. if it fails, continue looping.
        return 1;                               # if it matches, return not-false.
    }
    return;                                     # if this is reached, we failed; find another word.
}