#!/usr/bin/perl -w

use v5.38;

$/ = "\n\n";
my %dirs;
my @steps = split //, scalar <>;
pop @steps;
pop @steps;
my $l = <>;
for (split /\n/, $l) {
	my @x = /[A-Z0-9]{3}/g;
	$dirs{$x[0].'L'} = $x[1];
	$dirs{$x[0].'R'} = $x[2];
}

my %seen;
my %now = map { substr($_, 0, 3) . $steps[0] => 1 } grep { /^..A/ } keys %dirs;
my @now = keys %now;
say join(' ', @now);

sub walk {
	my $node = shift;
	my $i = 0;
	my $n;
	while ($node !~ /^..Z/) {
		$i++;
		$i = 0 if $i >= @steps;
		$node = $dirs{$node} . $steps[$i];
	$n++;
	}
	return $n;
}

my %f;
use List::Util qw(product);
for (@now) {
	my $st = walk($_);
	my $l = `factor $st`;
	$l =~ s/.*://;
	for my $n ($l =~ /\d+/g) {
		$f{$n}++;
	}
}
say product keys %f;
