fn gcd(u w : int) : int
[
	while w <> 0 do
		u, w := w, u mod w;
	return u;
]

fn lcm(u w : int) := u div gcd(u, w) * w;

fn decode_char(b : byte) : int
[
	if b >= '0', b <= '9' then return b - '0';
	if b >= 'A', b <= 'Z' then return b - 'A' + 10;
	abort;
]

fn decode(b : bytes) := (36 * 36) * decode_char(b[0]) + 36 * decode_char(b[1]) + decode_char(b[2]);

fn main
[
	var lines := list_break_to_lines(read_lazy(h[0]));

	var steps := lines[0];
	lines := lines[2 .. ];
	var a := array_fill(mktuple3(-1, -1, false), [ipower(36, 3)]);
	var pos := empty(int);
	for line in lines do [
		var id := decode(line[ .. 3]);
		var left := decode(line[7 .. 10]);
		var right := decode(line[12 .. 15]);
		a[id].v1 := left;
		a[id].v2 := right;
		if line[2] = 'A' then
			pos +<= id;
		if line[2] = 'Z' then
			a[id].v3 := true;
	]
	var counter := 0;
	var finished := fill(-1, len(pos));
	while true do [
		for i := 0 to len(pos) do [
			if a[pos[i]].v3 then [
				if finished[i] <> -1 then
					continue;
				finished[i] := counter;
			]
		]
		if list_search(finished, -1) = -1 then
			break;
		var stp := steps[counter mod len(steps)];
		for i := 0 to len(pos) do [
			if stp = 'L' then
				pos[i] := a[pos[i]].v1;
			else if stp = 'R' then
				pos[i] := a[pos[i]].v2;
			else
				abort;
		]
		counter += 1;
	]
	var g := list_fold(1, finished, lcm);
	write(h[1], ntos(g) + nl);
]