#! /usr/bin/perl
use strict;
use warnings;

my $last_entry = <>;
my $last_signal = <>;
chomp $last_signal;
my @rules = (<>);
my $instring = pop @rules;
my $lines_printed = 0;
my $eof_seen = undef;

sub signal_to_commands {
    my $signal = shift;
    my $signum = ord(lc $signal) - ord('a');
    lc($signal) gt lc($last_signal) and $eof_seen = 1;
    my $direction = ($signal eq lc($signal)) ? '-' : '+';
    $direction x (($last_entry + 1) << $signum)
}

sub convert {
    my $commands = shift;
    $commands =~ s/(?<![0-9.])(\d+)/('+'x$1).'^'.('-'x$1)/ge;
    $commands =~ s/([a-zA-Z])/signal_to_commands($1)/ge;
    1 while $commands =~ s/\-\+//g;
    1 while $commands =~ s/\+\-//g;
    $commands;
}

sub gen_states {
    my $seen_signals = shift;

    if (!scalar @_) {
        for my $entry (0..$last_entry) {
            my $most_requirements = -1;
            my $best_rhs = $entry;
            for my $rule (@rules) {
                $rule =~ /^(\d+)(\S*)\s+(.*)/ or die "Malformed rule '$rule'";
                $1 == $entry or next;
                my $rhs = $3;
                my @requirements = split '', $2;
                scalar(@requirements) > $most_requirements or next;
                if (@requirements)  {
                    my $re = join '.*', sort {(lc $b) cmp (lc $a)} @requirements;
                    $seen_signals =~ $re or next;
                }
                $most_requirements = scalar(@requirements);
                $best_rhs = $rhs;
            }
            
            $best_rhs = convert $best_rhs;
            print "$best_rhs\n";
            ++$lines_printed;
        }
    } else {
        my $this_signal = pop @_;
        gen_states ($seen_signals . lc($this_signal), @_);
        gen_states ($seen_signals . uc($this_signal), @_);
    }
}

gen_states '', 'a' .. $last_signal;
$eof_seen and print "\n" x $lines_printed;

print convert($instring);