#include <iostream>
#include <cstring>
using namespace std ;
int mask = 0xfb9df ;
const int NMOVES = 16 ;
const int FACES = 20 ;
struct cmet {
   cmet() ;
   char c[FACES] ;
   void move(int m) ;
   void move(const char *c) ;
   static void initmovtab() ;
} ;
cmet::cmet() {
   for (int i=0; i<FACES; i++)
      c[i] = i ;
   for (int i=0; i<FACES; i++)
      if (((1 << i) & mask) == 0)
         c[i] = FACES ;
}
int ballofmove[] = { 0, 0, 1, 1, 2, 2, 3, 3, 0, 0, 2, 2, 1, 1, 3, 3 } ;
int ballofpos[] =
         {0, 1, 0, 0, 0, 4, 1, 1, 1, 4, 4, 2, 2, 2, 4, 3, 3, 3, 2, 3, 4} ;
char *cmoves[] = { "aR", "aL", "bR", "bL", "dR", "dL", "cR", "cL",
                   "aD", "aU", "dD", "dU", "bD", "bU", "cD", "cU" } ;
#define ROT(d,e,f,g) {int t=c[d];c[d]=c[e];c[e]=c[f];c[f]=c[g];c[g]=t;}break;
#define FH(v) ROT(v,v+1,v+3,v+2)
#define BH(v) ROT(v,v+2,v+3,v+1)
#define FV1(v) ROT(v,v+3,v+9,v+4)
#define BV1(v) ROT(v,v+4,v+9,v+3)
#define FV2(v) ROT(v,v+5,v+9,v+6)
#define BV2(v) ROT(v,v+6,v+9,v+5)
void cmet::move(int m) {
   switch (m) {
case 0: FH(2) ; case 1: BH(2) ;
case 2: FH(5) ; case 3: BH(5) ;
case 4: FH(11) ; case 5: BH(11) ;
case 6: FH(14) ; case 7: BH(14) ;
case 8: FV1(0) ; case 9: BV1(0) ;
case 10: FV1(9) ; case 11: BV1(9) ;
case 12: FV2(1) ; case 13: BV2(1) ;
case 14: FV2(10) ; case 15: BV2(10) ;
   }
}
int movtab[NMOVES][FACES] ;
int dist0[FACES+1][FACES+1] ;
int dist1[FACES+1][FACES+1] ;
void cmet::initmovtab() {
   int omask = mask ;
   mask = -1 ;
   for (int i=0; i<NMOVES; i++) {
      cmet cp ;
      cp.move(i) ;
      for (int j=0; j<FACES; j++)
         movtab[i][cp.c[j]] = j ;
   }
   mask = omask ;
   cmet cp ;
   for (int i=0; i<=FACES; i++) {
      for (int j=0; j<=FACES; j++) {
         dist0[i][j] = dist1[i][j] = 1000 ;
      }
      dist0[i][i] = dist1[i][i] = 0 ;
   }
   for (int i=0; i<FACES; i++) {
      dist1[i][cp.c[i]] = dist0[i][cp.c[i]] = 0 ;
   }
   for (int i=0; i<NMOVES; i++) {
      for (int j=0; j<FACES; j++) {
         int k = movtab[i][j] ;
         if (dist0[j][k] > 1)
            dist0[j][k] = 1 ;
         if (cp.c[j] == FACES || cp.c[k] == FACES) {
            if (dist1[j][k] > 1)
               dist1[j][k] = 1 ;
         } else {
            if (dist1[j][k] > 0)
               dist1[j][k] = 0 ;
         }
      }
   }
   for (int k=0; k<=FACES; k++)
      for (int i=0; i<=FACES; i++)
         for (int j=0; j<=FACES; j++) {
            if (dist0[i][k] + dist0[k][j] <  dist0[i][j])
               dist0[i][j] = dist0[i][k] + dist0[k][j] ;
            if (dist1[i][k] + dist1[k][j] <  dist1[i][j])
               dist1[i][j] = dist1[i][k] + dist1[k][j] ;
         }
}
int ball1[5][5] = {{0, 5, 9, 0, 0}, {5, 0, 0, 10, 0}, {9, 0, 0, 14, 0},
                   {0, 10, 14, 0, 0}, {0, 0, 0, 0, 0}} ;
int bn[4] = { 5, 9, 10, 14 } ;
int opp[21] = { 9, 10, 5, 0, 0, 0, 0, 0, 5, 0, 0, 14, 0, 0, 0, 0, 0, 14, 5, 9, 0 } ;
int calcdist(const cmet &cp) {
   int d0=0, d1=0 ;
   for (int i=0; i<FACES; i++) {
      d0 += dist0[i][cp.c[i]] ;
      d1 += dist1[i][cp.c[i]] ;
   }
   int nd0 = (d0 + 3) / 4 ;
   int nd1 = (d1 + 1) / 2 ;
   // how many blockers do we need to move?
   int used = 0 ;
   for (int i=0; i<FACES; i++) {
      int nb = ball1[ballofpos[i]][ballofpos[cp.c[i]]] ;
      if (nb && cp.c[nb] == FACES && (used & (1 << nb)) == 0) {
         nd1++ ;
         used |= (1 << nb) ;
      }
      nb = opp[i] ;
      if (nb && cp.c[i] != i && cp.c[nb] == FACES && (used & (1 << nb)) == 0) {
         nd1++ ;
         used |= (1 << nb) ;
      }
   }
   int r = (nd0 > nd1 ? nd0 : nd1) ;
   return r ;
}
void error(const char *s) {
   cerr << s << endl ;
   exit(10) ;
}
long long steps = 0 ;
int moves[100] ;
int all = 0 ;
int sols = 0 ;
int od = 0 ;
int solver(const cmet &cp, int togo, int lastmove, int lastdup) {
   steps++ ;
   int d = calcdist(cp) ;
   if (d == 0) {
      if (!all)
         return 1 ;
      for (int i=od; i>0; i--)
         cout << " " << cmoves[moves[i]] ;
      cout << endl ;
      sols++ ;
      return 0 ;
   }
   if (d > togo)
      return 0 ;
   for (int m=0; m<NMOVES; m++) {
      if (m == lastmove && (lastdup || (m & 1)))
         continue ;
      if ((m ^ lastmove) == 1)
         continue ;
      if (m > lastmove && ((m ^ lastmove) & ~3) != 0 &&
          ballofmove[m] != ballofmove[lastmove])
         continue ;
      moves[togo] = m ;
      cmet cp2 = cp ;
      cp2.move(m) ;
      int t = solver(cp2, togo-1, m, m==lastmove) ;
      if (t)
         return 1 ;
   }
   return 0 ;
}
int solveseq = 0 ;
void solve(const cmet &cp) {
   int d = calcdist(cp) ;
   steps = 0 ;
   sols = 0 ;
   solveseq++ ;
   cout << solveseq << ": Initial " << d << " " << flush ;
   for (; 1; d++) {
      od = d ;
      int succ = solver(cp, d, 1000, 0) ;
      if (succ || sols) {
         cout << "Solved at depth " << d << " in " << steps << endl ;
         if (!all) {
            for (int i=d; i>0; i--)
               cout << " " << cmoves[moves[i]] ;
            cout << endl ;
         }
         return ;
      } else {
         cout << "[" << d << "]" << flush ;
      }
   }
}
void cmet::move(const char *s) {
   for (int t=0; t<NMOVES; t++) {
      if (strcmp(cmoves[t], s) == 0) {
         cout << s << " move is " << t << endl ;
         move(t) ;
         return ;
      }
   }
   error("! Could not find move") ;
}
int main(int argc, char *argv[]) {
   cmet::initmovtab() ;
   cmet cp ;
   if (argc > 1) {
      for (int i=1; i<argc; i++)
         cp.move(argv[i]) ;
      for (int i=0; i<FACES; i++)
         cout << " " << (int)cp.c[i] ;
      cout << endl ;
      solve(cp) ;
   } else {
      while (1) {
         /* Jaap: I changed the following line from
          *  int m = (int)(FACES*drand48()) ;
          * since drand48 is not available on all C implementations.
          */
         int m = (int)(FACES*rand()/RAND_MAX) ;
         cp.move(m) ;
         solve(cp) ;
      }
   }
   return 0 ;
}