using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode.QuestionBank.Question1138
{
    public class Solution1138_2 : Interface1138
    {
        private static readonly Dictionary<int, string> map = new Dictionary<int, string>()
        {
            {0,"!"}, {1,"R!"}, {2,"RR!"}, {3,"RRR!"}, {4,"RRRR!"}, {5,"D!"}, {6,"DR!"}, {7,"DRR!"}, {8,"DRRR!"}, {9,"DRRRR!"}, {10,"DD!"}, {11,"DDR!"}, {12,"DDRR!"}, {13,"DDRRR!"}, {14,"DDRRRR!"}, {15,"DDD!"}, {16,"DDDR!"}, {17,"DDDRR!"}, {18,"DDDRRR!"}, {19,"DDDRRRR!"}, {20,"DDDD!"}, {21,"DDDDR!"}, {22,"DDDDRR!"}, {23,"DDDDRRR!"}, {24,"DDDDRRRR!"}, {25,"DDDDD!"},
            {26,"L!"}, {27,"!"}, {28,"R!"}, {29,"RR!"}, {30,"RRR!"}, {31,"LD!"}, {32,"D!"}, {33,"DR!"}, {34,"DRR!"}, {35,"DRRR!"}, {36,"LDD!"}, {37,"DD!"}, {38,"DDR!"}, {39,"DDRR!"}, {40,"DDRRR!"}, {41,"LDDD!"}, {42,"DDD!"}, {43,"DDDR!"}, {44,"DDDRR!"}, {45,"DDDRRR!"}, {46,"LDDDD!"}, {47,"DDDD!"}, {48,"DDDDR!"}, {49,"DDDDRR!"}, {50,"DDDDRRR!"}, {51,"LDDDDD!"},
            {52,"LL!"}, {53,"L!"}, {54,"!"}, {55,"R!"}, {56,"RR!"}, {57,"LLD!"}, {58,"LD!"}, {59,"D!"}, {60,"DR!"}, {61,"DRR!"}, {62,"LLDD!"}, {63,"LDD!"}, {64,"DD!"}, {65,"DDR!"}, {66,"DDRR!"}, {67,"LLDDD!"}, {68,"LDDD!"}, {69,"DDD!"}, {70,"DDDR!"}, {71,"DDDRR!"}, {72,"LLDDDD!"}, {73,"LDDDD!"}, {74,"DDDD!"}, {75,"DDDDR!"}, {76,"DDDDRR!"}, {77,"LLDDDDD!"},
            {78,"LLL!"}, {79,"LL!"}, {80,"L!"}, {81,"!"}, {82,"R!"}, {83,"LLLD!"}, {84,"LLD!"}, {85,"LD!"}, {86,"D!"}, {87,"DR!"}, {88,"LLLDD!"}, {89,"LLDD!"}, {90,"LDD!"}, {91,"DD!"}, {92,"DDR!"}, {93,"LLLDDD!"}, {94,"LLDDD!"}, {95,"LDDD!"}, {96,"DDD!"}, {97,"DDDR!"}, {98,"LLLDDDD!"}, {99,"LLDDDD!"}, {100,"LDDDD!"}, {101,"DDDD!"}, {102,"DDDDR!"}, {103,"LLLDDDDD!"},
            {104,"LLLL!"}, {105,"LLL!"}, {106,"LL!"}, {107,"L!"}, {108,"!"}, {109,"LLLLD!"}, {110,"LLLD!"}, {111,"LLD!"}, {112,"LD!"}, {113,"D!"}, {114,"LLLLDD!"}, {115,"LLLDD!"}, {116,"LLDD!"}, {117,"LDD!"}, {118,"DD!"}, {119,"LLLLDDD!"}, {120,"LLLDDD!"}, {121,"LLDDD!"}, {122,"LDDD!"}, {123,"DDD!"}, {124,"LLLLDDDD!"}, {125,"LLLDDDD!"}, {126,"LLDDDD!"}, {127,"LDDDD!"}, {128,"DDDD!"}, {129,"LLLLDDDDD!"},
            {130,"U!"}, {131,"UR!"}, {132,"URR!"}, {133,"URRR!"}, {134,"URRRR!"}, {135,"!"}, {136,"R!"}, {137,"RR!"}, {138,"RRR!"}, {139,"RRRR!"}, {140,"D!"}, {141,"DR!"}, {142,"DRR!"}, {143,"DRRR!"}, {144,"DRRRR!"}, {145,"DD!"}, {146,"DDR!"}, {147,"DDRR!"}, {148,"DDRRR!"}, {149,"DDRRRR!"}, {150,"DDD!"}, {151,"DDDR!"}, {152,"DDDRR!"}, {153,"DDDRRR!"}, {154,"DDDRRRR!"}, {155,"DDDD!"},
            {156,"UL!"}, {157,"U!"}, {158,"UR!"}, {159,"URR!"}, {160,"URRR!"}, {161,"L!"}, {162,"!"}, {163,"R!"}, {164,"RR!"}, {165,"RRR!"}, {166,"LD!"}, {167,"D!"}, {168,"DR!"}, {169,"DRR!"}, {170,"DRRR!"}, {171,"LDD!"}, {172,"DD!"}, {173,"DDR!"}, {174,"DDRR!"}, {175,"DDRRR!"}, {176,"LDDD!"}, {177,"DDD!"}, {178,"DDDR!"}, {179,"DDDRR!"}, {180,"DDDRRR!"}, {181,"LDDDD!"},
            {182,"ULL!"}, {183,"UL!"}, {184,"U!"}, {185,"UR!"}, {186,"URR!"}, {187,"LL!"}, {188,"L!"}, {189,"!"}, {190,"R!"}, {191,"RR!"}, {192,"LLD!"}, {193,"LD!"}, {194,"D!"}, {195,"DR!"}, {196,"DRR!"}, {197,"LLDD!"}, {198,"LDD!"}, {199,"DD!"}, {200,"DDR!"}, {201,"DDRR!"}, {202,"LLDDD!"}, {203,"LDDD!"}, {204,"DDD!"}, {205,"DDDR!"}, {206,"DDDRR!"}, {207,"LLDDDD!"},
            {208,"ULLL!"}, {209,"ULL!"}, {210,"UL!"}, {211,"U!"}, {212,"UR!"}, {213,"LLL!"}, {214,"LL!"}, {215,"L!"}, {216,"!"}, {217,"R!"}, {218,"LLLD!"}, {219,"LLD!"}, {220,"LD!"}, {221,"D!"}, {222,"DR!"}, {223,"LLLDD!"}, {224,"LLDD!"}, {225,"LDD!"}, {226,"DD!"}, {227,"DDR!"}, {228,"LLLDDD!"}, {229,"LLDDD!"}, {230,"LDDD!"}, {231,"DDD!"}, {232,"DDDR!"}, {233,"LLLDDDD!"},
            {234,"ULLLL!"}, {235,"ULLL!"}, {236,"ULL!"}, {237,"UL!"}, {238,"U!"}, {239,"LLLL!"}, {240,"LLL!"}, {241,"LL!"}, {242,"L!"}, {243,"!"}, {244,"LLLLD!"}, {245,"LLLD!"}, {246,"LLD!"}, {247,"LD!"}, {248,"D!"}, {249,"LLLLDD!"}, {250,"LLLDD!"}, {251,"LLDD!"}, {252,"LDD!"}, {253,"DD!"}, {254,"LLLLDDD!"}, {255,"LLLDDD!"}, {256,"LLDDD!"}, {257,"LDDD!"}, {258,"DDD!"}, {259,"LLLLDDDD!"},
            {260,"UU!"}, {261,"UUR!"}, {262,"UURR!"}, {263,"UURRR!"}, {264,"UURRRR!"}, {265,"U!"}, {266,"UR!"}, {267,"URR!"}, {268,"URRR!"}, {269,"URRRR!"}, {270,"!"}, {271,"R!"}, {272,"RR!"}, {273,"RRR!"}, {274,"RRRR!"}, {275,"D!"}, {276,"DR!"}, {277,"DRR!"}, {278,"DRRR!"}, {279,"DRRRR!"}, {280,"DD!"}, {281,"DDR!"}, {282,"DDRR!"}, {283,"DDRRR!"}, {284,"DDRRRR!"}, {285,"DDD!"},
            {286,"UUL!"}, {287,"UU!"}, {288,"UUR!"}, {289,"UURR!"}, {290,"UURRR!"}, {291,"UL!"}, {292,"U!"}, {293,"UR!"}, {294,"URR!"}, {295,"URRR!"}, {296,"L!"}, {297,"!"}, {298,"R!"}, {299,"RR!"}, {300,"RRR!"}, {301,"LD!"}, {302,"D!"}, {303,"DR!"}, {304,"DRR!"}, {305,"DRRR!"}, {306,"LDD!"}, {307,"DD!"}, {308,"DDR!"}, {309,"DDRR!"}, {310,"DDRRR!"}, {311,"LDDD!"},
            {312,"UULL!"}, {313,"UUL!"}, {314,"UU!"}, {315,"UUR!"}, {316,"UURR!"}, {317,"ULL!"}, {318,"UL!"}, {319,"U!"}, {320,"UR!"}, {321,"URR!"}, {322,"LL!"}, {323,"L!"}, {324,"!"}, {325,"R!"}, {326,"RR!"}, {327,"LLD!"}, {328,"LD!"}, {329,"D!"}, {330,"DR!"}, {331,"DRR!"}, {332,"LLDD!"}, {333,"LDD!"}, {334,"DD!"}, {335,"DDR!"}, {336,"DDRR!"}, {337,"LLDDD!"},
            {338,"UULLL!"}, {339,"UULL!"}, {340,"UUL!"}, {341,"UU!"}, {342,"UUR!"}, {343,"ULLL!"}, {344,"ULL!"}, {345,"UL!"}, {346,"U!"}, {347,"UR!"}, {348,"LLL!"}, {349,"LL!"}, {350,"L!"}, {351,"!"}, {352,"R!"}, {353,"LLLD!"}, {354,"LLD!"}, {355,"LD!"}, {356,"D!"}, {357,"DR!"}, {358,"LLLDD!"}, {359,"LLDD!"}, {360,"LDD!"}, {361,"DD!"}, {362,"DDR!"}, {363,"LLLDDD!"},
            {364,"UULLLL!"}, {365,"UULLL!"}, {366,"UULL!"}, {367,"UUL!"}, {368,"UU!"}, {369,"ULLLL!"}, {370,"ULLL!"}, {371,"ULL!"}, {372,"UL!"}, {373,"U!"}, {374,"LLLL!"}, {375,"LLL!"}, {376,"LL!"}, {377,"L!"}, {378,"!"}, {379,"LLLLD!"}, {380,"LLLD!"}, {381,"LLD!"}, {382,"LD!"}, {383,"D!"}, {384,"LLLLDD!"}, {385,"LLLDD!"}, {386,"LLDD!"}, {387,"LDD!"}, {388,"DD!"}, {389,"LLLLDDD!"},
            {390,"UUU!"}, {391,"UUUR!"}, {392,"UUURR!"}, {393,"UUURRR!"}, {394,"UUURRRR!"}, {395,"UU!"}, {396,"UUR!"}, {397,"UURR!"}, {398,"UURRR!"}, {399,"UURRRR!"}, {400,"U!"}, {401,"UR!"}, {402,"URR!"}, {403,"URRR!"}, {404,"URRRR!"}, {405,"!"}, {406,"R!"}, {407,"RR!"}, {408,"RRR!"}, {409,"RRRR!"}, {410,"D!"}, {411,"DR!"}, {412,"DRR!"}, {413,"DRRR!"}, {414,"DRRRR!"}, {415,"DD!"},
            {416,"UUUL!"}, {417,"UUU!"}, {418,"UUUR!"}, {419,"UUURR!"}, {420,"UUURRR!"}, {421,"UUL!"}, {422,"UU!"}, {423,"UUR!"}, {424,"UURR!"}, {425,"UURRR!"}, {426,"UL!"}, {427,"U!"}, {428,"UR!"}, {429,"URR!"}, {430,"URRR!"}, {431,"L!"}, {432,"!"}, {433,"R!"}, {434,"RR!"}, {435,"RRR!"}, {436,"LD!"}, {437,"D!"}, {438,"DR!"}, {439,"DRR!"}, {440,"DRRR!"}, {441,"LDD!"},
            {442,"UUULL!"}, {443,"UUUL!"}, {444,"UUU!"}, {445,"UUUR!"}, {446,"UUURR!"}, {447,"UULL!"}, {448,"UUL!"}, {449,"UU!"}, {450,"UUR!"}, {451,"UURR!"}, {452,"ULL!"}, {453,"UL!"}, {454,"U!"}, {455,"UR!"}, {456,"URR!"}, {457,"LL!"}, {458,"L!"}, {459,"!"}, {460,"R!"}, {461,"RR!"}, {462,"LLD!"}, {463,"LD!"}, {464,"D!"}, {465,"DR!"}, {466,"DRR!"}, {467,"LLDD!"},
            {468,"UUULLL!"}, {469,"UUULL!"}, {470,"UUUL!"}, {471,"UUU!"}, {472,"UUUR!"}, {473,"UULLL!"}, {474,"UULL!"}, {475,"UUL!"}, {476,"UU!"}, {477,"UUR!"}, {478,"ULLL!"}, {479,"ULL!"}, {480,"UL!"}, {481,"U!"}, {482,"UR!"}, {483,"LLL!"}, {484,"LL!"}, {485,"L!"}, {486,"!"}, {487,"R!"}, {488,"LLLD!"}, {489,"LLD!"}, {490,"LD!"}, {491,"D!"}, {492,"DR!"}, {493,"LLLDD!"},
            {494,"UUULLLL!"}, {495,"UUULLL!"}, {496,"UUULL!"}, {497,"UUUL!"}, {498,"UUU!"}, {499,"UULLLL!"}, {500,"UULLL!"}, {501,"UULL!"}, {502,"UUL!"}, {503,"UU!"}, {504,"ULLLL!"}, {505,"ULLL!"}, {506,"ULL!"}, {507,"UL!"}, {508,"U!"}, {509,"LLLL!"}, {510,"LLL!"}, {511,"LL!"}, {512,"L!"}, {513,"!"}, {514,"LLLLD!"}, {515,"LLLD!"}, {516,"LLD!"}, {517,"LD!"}, {518,"D!"}, {519,"LLLLDD!"},
            {520,"UUUU!"}, {521,"UUUUR!"}, {522,"UUUURR!"}, {523,"UUUURRR!"}, {524,"UUUURRRR!"}, {525,"UUU!"}, {526,"UUUR!"}, {527,"UUURR!"}, {528,"UUURRR!"}, {529,"UUURRRR!"}, {530,"UU!"}, {531,"UUR!"}, {532,"UURR!"}, {533,"UURRR!"}, {534,"UURRRR!"}, {535,"U!"}, {536,"UR!"}, {537,"URR!"}, {538,"URRR!"}, {539,"URRRR!"}, {540,"!"}, {541,"R!"}, {542,"RR!"}, {543,"RRR!"}, {544,"RRRR!"}, {545,"D!"},
            {546,"UUUUL!"}, {547,"UUUU!"}, {548,"UUUUR!"}, {549,"UUUURR!"}, {550,"UUUURRR!"}, {551,"UUUL!"}, {552,"UUU!"}, {553,"UUUR!"}, {554,"UUURR!"}, {555,"UUURRR!"}, {556,"UUL!"}, {557,"UU!"}, {558,"UUR!"}, {559,"UURR!"}, {560,"UURRR!"}, {561,"UL!"}, {562,"U!"}, {563,"UR!"}, {564,"URR!"}, {565,"URRR!"}, {566,"L!"}, {567,"!"}, {568,"R!"}, {569,"RR!"}, {570,"RRR!"}, {571,"LD!"},
            {572,"UUUULL!"}, {573,"UUUUL!"}, {574,"UUUU!"}, {575,"UUUUR!"}, {576,"UUUURR!"}, {577,"UUULL!"}, {578,"UUUL!"}, {579,"UUU!"}, {580,"UUUR!"}, {581,"UUURR!"}, {582,"UULL!"}, {583,"UUL!"}, {584,"UU!"}, {585,"UUR!"}, {586,"UURR!"}, {587,"ULL!"}, {588,"UL!"}, {589,"U!"}, {590,"UR!"}, {591,"URR!"}, {592,"LL!"}, {593,"L!"}, {594,"!"}, {595,"R!"}, {596,"RR!"}, {597,"LLD!"},
            {598,"UUUULLL!"}, {599,"UUUULL!"}, {600,"UUUUL!"}, {601,"UUUU!"}, {602,"UUUUR!"}, {603,"UUULLL!"}, {604,"UUULL!"}, {605,"UUUL!"}, {606,"UUU!"}, {607,"UUUR!"}, {608,"UULLL!"}, {609,"UULL!"}, {610,"UUL!"}, {611,"UU!"}, {612,"UUR!"}, {613,"ULLL!"}, {614,"ULL!"}, {615,"UL!"}, {616,"U!"}, {617,"UR!"}, {618,"LLL!"}, {619,"LL!"}, {620,"L!"}, {621,"!"}, {622,"R!"}, {623,"LLLD!"},
            {624,"UUUULLLL!"}, {625,"UUUULLL!"}, {626,"UUUULL!"}, {627,"UUUUL!"}, {628,"UUUU!"}, {629,"UUULLLL!"}, {630,"UUULLL!"}, {631,"UUULL!"}, {632,"UUUL!"}, {633,"UUU!"}, {634,"UULLLL!"}, {635,"UULLL!"}, {636,"UULL!"}, {637,"UUL!"}, {638,"UU!"}, {639,"ULLLL!"}, {640,"ULLL!"}, {641,"ULL!"}, {642,"UL!"}, {643,"U!"}, {644,"LLLL!"}, {645,"LLL!"}, {646,"LL!"}, {647,"L!"}, {648,"!"}, {649,"LLLLD!"},
            {650,"UUUUU!"}, {651,"UUUUUR!"}, {652,"UUUUURR!"}, {653,"UUUUURRR!"}, {654,"UUUUURRRR!"}, {655,"UUUU!"}, {656,"UUUUR!"}, {657,"UUUURR!"}, {658,"UUUURRR!"}, {659,"UUUURRRR!"}, {660,"UUU!"}, {661,"UUUR!"}, {662,"UUURR!"}, {663,"UUURRR!"}, {664,"UUURRRR!"}, {665,"UU!"}, {666,"UUR!"}, {667,"UURR!"}, {668,"UURRR!"}, {669,"UURRRR!"}, {670,"U!"}, {671,"UR!"}, {672,"URR!"}, {673,"URRR!"}, {674,"URRRR!"}, {675,"!"},
        };

        /// <summary>
        /// 打表
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        public string AlphabetBoardPath(string target)
        {
            StringBuilder result = new StringBuilder();
            int src = 0, tgt;
            for (int i = 0; i < target.Length; i++)
            {
                tgt = target[i] - 'a';
                result.Append(map[src * 26 + tgt]);
                src = tgt;
            }

            return result.ToString();
        }
    }
}
