using System.Collections.Generic;
using System.Text.RegularExpressions;
using static System.Console;
public static void Main()
var lines = Input.Split("\n");
var instructions = lines[0];
var nodePattern = new Regex(@"(\w+) = \((\w+), (\w+)\)", RegexOptions.Compiled);
.Select(line => nodePattern.Match(line))
.ToDictionary(line => line.Groups[1].Value, line => (line.Groups[2].Value, line.Groups[3].Value));
.Where(_ => _.Last() == 'A')
var cycles = new List<(long, long)>();
var visited = new Dictionary<(string, int), long> { { (ps, 0), 0 } };
p = instructions[i] == 'L' ? o.Item1 : o.Item2;
i = (i + 1) % instructions.Length;
if (visited.ContainsKey((p, i)))
var e = visited.Where(_ => _.Key.Item1.Last() == 'Z').Select(_ => _.Value).Single();
WriteLine($"{ps}:{f}:{steps + 1}:{e}");
cycles.Add((e, steps - f));
visited.Add((p, i), steps);
if (cycles.Where(_ => _.Item1 != _.Item2).Any())
throw new Exception("Not expected");
static long Gcd(long a, long b)
static long Lcm(long a, long b) => a * b / Gcd(a, b);
var ans = cycles.Aggregate(1L, (acc, v) => Lcm(acc, v.Item1));
private const string Input1 = """
private const string Input2 = """
private const string Input3 = """
private const string Input = """
LLLLLLLRRRLRRRLRLRLRLRRLLRRRLRLLRRRLLRRLRRLRRLRLRRLRLRRRLRRLRLRRRLRRLRRLRLRRLLRLLRLRRRLRRLRLLLLRRLLLLRLRLRLRRRLRLRLLLRLRRRLRRRLRRRLRLRRLRRRLRLLLRLLRRLRRRLRRLRRLRRLRLRRRLRLRLRLLRRRLRRRLRRLRRRLLLRRLRRLRRRLRLRRRLRRRLRLRRLRRRLRLRRLRLRRLRRRLRLRRLRLLRRRLLRLRRLRRRLLLRLRRLRRRR