using System;
using System.Collections.Generic;
using System.Security.Cryptography;
using System.Text;

namespace D17._1
{
    class Program
    {
        static byte[] ToB(string str) => Encoding.ASCII.GetBytes(str);
        static string ToS(byte[] b) => BitConverter.ToString(b).Replace("-", "");

        private static string GetHash(string input, string sequence, MD5 md5) => ToS(md5.ComputeHash(ToB($"{input}{sequence}")));

        static string SolveMaze((int x, int y) coord, (int x, int y) goal, string input)
        {
            var queue = new Queue<((int x, int y) coord, string sequence)>();
            string sequence = null;
            queue.Enqueue((coord, ""));

            var md5 = MD5.Create();

            while (queue.Count > 0)
            {
                var element = queue.Dequeue();
                coord = element.coord;
                sequence = element.sequence;

                if (coord == (3, 3))
                    break;

                var hash = GetHash(input, sequence, md5);
                for (int i = 0; i < 4; i++)
                {
                    if (hash[i] <= 'A') continue;

                    (int mx, int my) = MoveSequence[i];
                    (int x, int y) ncoord = (coord.x + mx, coord.y + my);

                    if (ncoord.x < 0 || ncoord.y < 0 || ncoord.x > 3 || ncoord.y > 3)
                        continue;

                    var nsequence = sequence + DoorSequence[i];

                    queue.Enqueue((ncoord, nsequence));
                }
            }

            md5.Dispose();
            return sequence;
        }

        static readonly char[] DoorSequence = new[] { 'U', 'D', 'L', 'R' };
        static readonly (int mx, int my)[] MoveSequence = new[] { (0, -1), (0, 1), (-1, 0), (1, 0) };
        static void Main(string[] args)
        {
            var seq = SolveMaze((0, 0), (3, 3), args[0]);

            Console.WriteLine($"Sequence is : {seq}");
        }
    }
}