#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include "assert.h"

using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define EACH(base, ii) for (typeof((base).begin()) ii = (base).begin(), base##ie = (base).end(); \
                            ii != base##ie; ++ii)

#define SIZE(X) ((int)(X.size()))//NOTES:SIZE(
#define LENGTH(X) ((int)(X.length()))//NOTES:LENGTH(
#define MP(X,Y) make_pair(X,Y)//NOTES:MP(
typedef long long int64;//NOTES:int64
typedef unsigned long long uint64;//NOTES:uint64
#define two(X) (1<<(X))//NOTES:two(
#define twoL(X) (((int64)(1))<<(X))//NOTES:twoL(
#define contain(S,X) (((S)&two(X))!=0)//NOTES:contain(
#define containL(S,X) (((S)&twoL(X))!=0)//NOTES:containL(
const double pi=acos(-1.0);//NOTES:pi
const double eps=1e-11;//NOTES:eps
template<class T> inline void checkmin(T &a,T b){if(b<a) a=b;}//NOTES:checkmin(
template<class T> inline void checkmax(T &a,T b){if(b>a) a=b;}//NOTES:checkmax(
typedef pair<int,int> ipair;//NOTES:ipair

typedef vector<int> ivector;
///////////////////////////////////////////////////////////////////////////////
static void
printPuzzle(int W, int H, string input) {
  int i;
  rep(i, input.size()) {
    if (i%W==0) printf("\n#");
    printf("%c", input[i]);
  }
  puts("");
}

///////////////////////////////////////////////////////////////////////////////
static string moves;
static bool useDistanceType = 2;

static bool useCache = false;
static bool flushCache = false;
static int maxCacheFilter = 200000;

static bool useYK = false;
static int maxYK = 10000;
static int typeYK = 1;

static int maxDepthFirstCount = 100;
static int numDepthFirst= 1;

static vector<string> resultList;
static map<string, string> cache;
static bool
addCache(string puzzle, string history) {
  if (!useCache) {
    return true;
  }
  map<string, string>::iterator it = cache.find(puzzle);
  if (it == cache.end()) {
    cache.insert(std::make_pair(puzzle, history));
    return true;
  } else {
    return false;
  }
}

static bool
makeCorrect(string input, string& output) {
  output.clear();
  char sample[]="123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ0";
  int i;
  rep(i, input.size()) {
    if (input[i] == '=') {
      output.push_back('=');
    } else {
      output.push_back(sample[i]);
    }
  }
  output[input.size()-1] = '0';
  return true;
}
static bool
checkCorrect(string input, string output) {
  return input == output;
}

static bool
reverse_history(string input, string &output) {
  int k;
  for (k=input.size(); k != 0; k--) {
    char move = input[k-1];
    switch(move) {
    case 'U': output.push_back('D'); break;
    case 'D': output.push_back('U'); break;
    case 'L': output.push_back('R'); break;
    case 'R': output.push_back('L'); break;
    default: break;
    }
  }
  return true;
}

static int
getPos(string input, char find) {
  int i;
  rep(i,input.size()) {
    if (input[i] == find) {
      return i;
    }
  }
  return -1;
}

static int
canMove(char move, int W, int H, string input, int pos) {

  int cx = pos%W;
  int cy = pos/W;
  int upx = 0;
  int upy = 0;
  if (move == 'U')        { upx = cx ; upy = cy - 1;
  } else if (move == 'D') { upx = cx ; upy = cy + 1;
  } else if (move == 'L') { upx = cx - 1; upy = cy;
  } else if (move == 'R') { upx = cx + 1; upy = cy;
  }

  if (upx < 0 || upx >= W) { return -1; }
  if (upy < 0 || upy >= H) { return -1; }

  int uppos = (upx) + (upy)*W;
  if (input[uppos] == '=') {
    return -1;
  }
  return uppos;
}

static bool
solvePuzzle(int W, int H, string input, string history) {
  int pos = getPos(input, '0');
  string dummy;
  int i; rep(i, input.size()) {
    dummy.push_back(input[i]);
  }
  string output;
  makeCorrect(dummy, output);

  int k;
  rep(k, history.size()) {
    int newpos=0;
    char move = history[k];
    if (move == '\n') break;
    newpos = canMove(move, W, H, dummy, pos);
    if (newpos == -1) {
      printf("#history[%d]=%c:newpos is outof bound\n", k, move);
      printf("#error:%s\n", history.c_str());
      printPuzzle(W, H, dummy);
      return false;
    }

    char tmp = dummy[newpos];
    dummy[newpos] = dummy[pos];
    dummy[pos] = tmp;
    pos = newpos;
  }
  if (checkCorrect(dummy, output)) {
    return true;
  } else {
    printf("#not equals to correct\n");
    printf("#error:%s\n", history.c_str());
    printPuzzle(W, H, dummy);
    return false;
  }
}

static bool
checkHistory(char move, string history) {
  int hsize = history.size();
  if (hsize != 0) {
    switch(history[hsize-1]) {
    case 'U': if (move == 'D') return false; break;
    case 'D': if (move == 'U') return false; break;
    case 'L': if (move == 'R') return false; break;
    case 'R': if (move == 'L') return false; break;
    }
  }
  return true;
}

static int
getNumTryMove(int W, int H, string input, string history, string &m) {
  int ret=0;
  int i;
  int pos = getPos(input, '0');
  rep(i, moves.size()) {
    if (checkHistory(moves[i], history) && canMove(moves[i], W, H, input, pos) != -1) {
      m.push_back(moves[i]);
      ret++;
    }
  }
  return ret;
}

static bool
tryMove(char move, int W, int H, string puzzle, string history,
             string& newpuz, string& newhis, string output) {
  if (!checkHistory(move, history)) {
    return false;
  }
  int pos = getPos(puzzle, '0');
  int uppos = canMove(move, W, H, puzzle, pos);
  if (uppos == -1) { return false; }
  {
    char swap = puzzle[uppos];
    newpuz = puzzle;
    newhis = history;

    newpuz[uppos] = '0';
    newpuz[pos] = swap;
    newhis.push_back(move);

    if (checkCorrect(newpuz, output)) {
      resultList.push_back(newhis);
    }
  }
  return addCache(newpuz, newhis);
}

static int
getDistancePenalty(int cost) {
    switch(cost) {
    case 0:
      return 0;
      break;
    case 1:
    case 2:
      return 2;
      break;
    case 3:
    case 4:
      return 3;
      break;
    case 5:
    case 6:
      return 4;
      break;
    case 7:
    case 8:
      return 5;
      break;
    default:
      return 6;
    }
}

static int
getWallPenalty(int W, int H, string input, int startpos, int endpos) {
  int cost=0;
  int sx = startpos%W;
  int sy = startpos/W;
  int ex = endpos%W;
  int ey = endpos/W;
  int k;

  if (sx == ex) {
    if (input[(sy+ey)/2*W+sx] == '=') {
      return 2;
    }
  }

  if (sy == ey) {
    if (input[sy*W+(sx+ex)/2] == '=') {
      return 2;
    }
  }

  if ((abs(sx-ex)+abs(sy-ey)) == 2) {
    // s=
    // =e
    if ((sx+1 == ex) && (sy+1 == ey)) {
      if ((input[sx+(sy+1)*W] == '=') && (input[(sx+1)+sy*W] == '=') ) {
        return 4;
      }
    }
    // =s
    // e=
    if ((sx-1 == ex) && (sy+1 == ey)) {
      if ((input[(sx-1)+sy*W] == '=') && (input[sx+(sy+1)*W] == '=')) {
        return 4;
      }
    }
    // e=
    // =s
    if ((sx-1 == ex) && (sy-1 == ey)) {
      if ((input[(sx-1)+sy*W] == '=') && (input[sx+(sy-1)*W] == '=')) {
        return 4;
      }
    }
    // =e
    // s=
    if ((sx+1 == ex) && (sy-1 == ey)) {
      if ((input[(sx+1)+sy*W] == '=') && (input[sx+(sy-1)*W] == '=')) {
        return 4;
      }
    }
  }
  return 0;
}

// otable
// output 2,2,3201
// mapping [value] --> pos : [0] = 2, [1] = 3, [2] = 1, [3] = 0;
static int otable[50];
static void mappingTable(string output, int table[]) {
  memset(table, -1, 50);
  {
    int i;
    rep(i,output.size()) {
      if (output[i] == '=') {
        //nop
      } else {
        if (output[i] <= '9') {
          table[output[i]-'0'] = i;
        } else {
          table[output[i]-'A'+10] = i;
        }
      }
    }
  }
}

static int
distanceH(int W, int H, string input, string output) {
  int ret=0;
  int pos;
  rep(pos, input.size()) {
    char t = input[pos];
    int opos = 0;

    if (t == '0' || t == '=') continue;
    if (t <= '9') {
//     assert(otable[t-'0'] != -1 && "assert");
      opos = otable[t-'0']; //'1'=49
    } else { //ABC
//      assert(otable[t-'A'+10] != -1 && "assert");
      opos = otable[t-'A'+10]; //'A'=65 A->10
    }
    {
      int tx = opos%W;
      int ty = opos/W;
      int x = pos%W;
      int y = pos/W;
      int cost = abs(tx-x) + abs(ty-y);
      cost += getWallPenalty(W, H, input, pos, opos);
      cost += getDistancePenalty(cost);
      ret += cost;
    }
  }
  return ret;
}

vector<ivector> distanceTable;

static void
updateDistance(int W, int H, int pos, int dis, string input, ivector& table) {
  ivector nextposs;
  ivector poss;
  int d = dis;

  table[pos] = d;
  d++;

  poss.push_back(pos);
  do {
    EACH(poss, ii) {
      int tpos = *ii;
      int k;
      rep(k, moves.size()) {
        int newPos = canMove(moves[k], W, H, input, tpos);
        if (newPos != -1) {
          if (table[newPos] == -1) {
            table[newPos] = d;
            nextposs.push_back(newPos);
          }
        }
      }
    }
    int k;
    poss.clear();
    rep(k, nextposs.size()) {
      poss.push_back(nextposs[k]);
    }
    nextposs.clear();
    d++;
  } while (poss.size());

//  int i; printf("distance table %d:", pos); rep(i, table.size()) { if (i%W==0) puts(""); printf("[%.2d]", table[i]); } puts("");
}

static void
initDistanceTable(int W, int H, string input) {
  distanceTable.clear();

  int size = input.size();
  int i,k;
  rep(i, size) {
    ivector table;
    rep(k, size) {
      if (input[k] == '=') {
        table.push_back(input[k]);
      } else {
        table.push_back(-1);
      }
    }
    updateDistance(W, H, i, 0, input, table);
    distanceTable.push_back(table);
  }
}

static int
distanceH2(int W, int H, string input, string output) {
  int ret=0;
  int size = input.size();
  int k;
  rep(k, size) {
    if (input[k] == '=') {
      continue;
    }
    char in = input[k];
    int opos = getPos(output, in);
    ivector table = distanceTable[k];
    int cost = table[opos];
//    cost += getDistancePenalty(cost);
    ret += cost;
  }
  return ret;
}

static int
distance(int W, int H, string input, string output) {
  if (useDistanceType == 1) {
    return distanceH(W, H, input, output);
  } else if (useDistanceType == 2) {
    return distanceH2(W, H, input, output);
  }
  return 0;
}

static int
filterCache(int W, int H, string output, int maxDistance) {
  int min = 1000;
  string minString;
  string minHistory;
  int num = 0;
  for (map<string, string>::iterator ii = cache.begin(), ie = cache.end();
       ii != ie;) {
    map<string, string>::iterator del = ii;
    ++ii;
    int d = distance(W,H, del->first, output);
    if (d > maxDistance) {
      cache.erase(del);
      num++;
    }
    else if (min > d) {
      min = d;
      minString = del->first;
      minHistory = del->second;
    }
  }
//printPuzzle(W, H, minString);
//printf("%s\n", minHistory.c_str());
  return num;
}

// false not found
static bool
tryDepthFirst(int W, int H, string puzzle, string history,
              string output, vector<pair<string, string> >&outList) {
  string m;
  int count = 0;
  int minDistance = 1000;

  vector<pair<string, string> > tmpList;
  vector<pair<string, string> > tryList;
  vector<pair<string, string> > nextList;

  {
    m.clear();
    int num = getNumTryMove(W, H, puzzle, history, m);
    if (num == 1) {
      // goto depth first iteration
    } else {
      return false;
    }
  }
  tryList.push_back(make_pair(puzzle, history));
retry:
  {
//printf("# depthfirst try=%d\n", count);
    EACH(tryList, mm) {
      string puz = mm->first;
      string his = mm->second;

      m.clear();
      int num = getNumTryMove(W, H, puz, his, m);
      if (num > numDepthFirst) {
        continue;
      }

      int k; rep(k, m.size()) {
        string newpuz;
        string newhis;
        if (tryMove(m[k], W, H, puz, his, newpuz, newhis, output)) {
          int score = distance(W,H,newpuz, output);
          checkmin(minDistance, score);

          tmpList.push_back(make_pair(newpuz, newhis));
          nextList.push_back(make_pair(newpuz, newhis));
          count++;
        }
      }
    }
    // max
    if (count > maxDepthFirstCount) {
//printf("#depthfirst max count over\n");
      tryList.clear();
      nextList.clear();
      goto finish;
    } else {
      tryList.clear();
      EACH(nextList, ii) {
        string f = ii->first;
        string s = ii->second;
        tryList.push_back(make_pair(f, s));
      }
      nextList.clear();
      if (tryList.size() != 0) goto retry;
    }
  }
finish:
  {
    EACH(tmpList, ii) {
      string f = ii->first;
      string s = ii->second;
      int score = distance(W, H, f,output);
      if ((minDistance + 10) > score) {
        outList.push_back(make_pair(f, s));
      }
    }
    tmpList.clear();
  }
  return true;
}

// x,y
// 0,0 1,0 2,0 | W = 3
// 0,1 1,1 2,1
// 0,2 1,2 2,2
// H = 3
static bool
solve(int maxMove, int maxResult, int W, int H, //W * H
      string input, string output) {
  cache.clear();
  resultList.clear();

  initDistanceTable(W, H, input); //need moves

  mappingTable(output, otable);

  vector<pair<string, string> > tryList;
  vector<pair<string, string> > tmpList;
  string zero; zero.clear();
  addCache(input, zero);
  tryList.push_back(make_pair(input, zero));

  int max = 0; //distance max
  int min = 0; //distance min
  int middle = 0;

  for (int m=1; m < maxMove; m++) {
printf("### try = %d ###\n", m);
    max = 0;
    min = 1000;
    EACH(tryList, mm) {
      string puzzle = mm->first;
      string history = mm->second;
      int score = distance(W,H,puzzle, output);
      checkmax(max, score);
      checkmin(min, score);

      int i;
      rep(i, moves.size()) {
        string puz;
        string his;
        if (tryMove(moves[i], W, H, puzzle, history, puz, his, output)) {
          tmpList.push_back(make_pair(puz, his));
          tryDepthFirst(W, H, puz, his, output, tmpList);
        }
      }

      if (resultList.size() >= maxResult) {
        return true;
      }
    }
    switch(typeYK) {
    case 1: {
        middle = (max + min) / 2;
        break;
      }
    case 2: {
        middle = max-2;
        if (tmpList.size() > 100000) {
          middle -=2;
        }
        if (middle < (min+10)) {  //12
          middle = max;
        }
        break;
      }
    case 3: {
        middle = (max + min) / 2 + 6;
        break;
      }
    }

//cache control
    if (flushCache && (cache.size() > 500000)) {
//      int delnum = filterCache(W, H, output, min+3);
      cache.clear();
    } else if (cache.size() > maxCacheFilter) {
      int delnum = filterCache(W, H, output, middle);
    }
printf("max=%d, min=%d, middle=%d\n", max, min, middle);
//printf("ListSize = %d\n", tmpList.size());
//printf("cacheSize = %d\n",cache.size());

    tryList.clear();
    if ((tmpList.size() > maxYK) && useYK) {
      EACH(tmpList, ii) {
        string puzzle = ii->first;
        string history= ii->second;
        int score = distance(W, H, puzzle, output);
        if (middle > score) {
          tryList.push_back(make_pair(puzzle, history));
        }
      }
    } else {
      EACH(tmpList, ii) {
        string puzzle = ii->first;
        string history= ii->second;
        tryList.push_back(make_pair(puzzle, history));
      }
    }
    tmpList.clear();
  }
  return false;
}

///////////////////////////////////////////////////////////////////////////////
static bool
test(int W, int H, string input) {
  string output;
  makeCorrect(input, output);
//  moves = string("UDLR");
  moves = string("ULRD");

  printf("in:%d,%d:%s\n", W, H, input.c_str());
  {
    resultList.clear();
    flushCache = false;
    useCache = true;

    useYK = true;
    maxYK = 30000;
    typeYK = 1;

    useDistanceType = 1;
    numDepthFirst=2;
    if (solve(100, 1, W, H, input, output)) {
      string history = resultList[0];
      if (solvePuzzle(W, H, input, history)) printf("1:%s\n", history.c_str());
      return true;
    }
  }
//  {
//    resultList.clear();
//    flushCache = true;
//    useCache = true;
//
//    useYK = true;
//    maxYK = 20000;
//    typeYK = 1;
//
//    useDistanceType = 1;
//
//    numDepthFirst=2;
//    if (solve(100, 1, W, H, output, input)) {
//      string history;
//      reverse_history(resultList[0], history);
//      if (solvePuzzle(W, H, input, history)) printf("3:%s\n", history.c_str());
//      return true;
//    }
//  }

//  {
//    resultList.clear();
//    flushCache = true;
//    useCache = true;
//
//    useYK = true;
//    maxYK = 5000;
//    typeYK = 2;
//
//    useDistanceType = 1;
//    numDepthFirst=2;
//    if (solve(300, 1, W, H, output, input)) {
//      string history;
//      reverse_history(resultList[0], history);
//
//      if (solvePuzzle(W, H, input, history)) printf("2:%s\n", history.c_str());
//      return true;
//    }
//  }

  puts("not found");
  return false;
}

int shell(int argc, char** argv) {
  int w;
  int h;

  if (argc != 2) {
    return -2;
  }
  w = argv[1][0] - '0';
  h = argv[1][2] - '0';
  string input(&argv[1][4], &argv[1][4+w*h]);
  test(w,h,input);
  return 0;
}

int main(int argc, char** argv) {
  shell(argc, argv);
  return 0;
}