#!/usr/bin/perl -w

use v5.38;
use List::Util 'uniq';

chomp(my $steps = <>);
my @steps = split //, $steps;

scalar <>;

my %dirs;
while (<>) {
	my @x = /\w{3}/g;
	$dirs{$x[0].'L'} = $x[1];
	$dirs{$x[0].'R'} = $x[2];
}

sub walk {
	my $now = shift;
	my $i = 0;
	while ($now !~ /Z$/) {
		$now = $dirs{$now . ($steps[$i++ % @steps])};
	}
	return $i;
}

sub gcd {
	my ($x, $y) = @_;
	($x, $y) = ($y, $x) if $y > $x;
	while ($y) {
		($x, $y) = ($y, $x % $y);
	}
	return $x;
}

# using LCM is incorrect in general case,
# but it works on the actual puzzle input
my $p;
for (uniq grep { /A$/ } map { substr($_, 0, 3) } keys %dirs) {
	my $steps = walk($_);
	if (defined $p) {
		$p *= $steps/gcd($p, $steps);
	} else {
		$p = $steps;
	}
}
say $p;
