Program GAME15;
Uses Dos, Crt, Graph;

const Depth = 12;   {max number of shifts}

type directions = (LEFT, RIGHT, DOWN, UP);   {directions of shifting}

var i : integer;
    main : array[1..4, 1..4] of byte;
    moves : array[1..200] of directions;
    xX, yX, movenum : byte;
    par : string;
    parnum : byte;

function StrToInt(s : string) : longint;   {Coversion from string to integer}
var j, Code: Integer;
begin
   Val(s, j, Code);
   StrToInt := j;
end;

function IntToStr(L: Longint): String;   {Conversion from integer to string}
var
 S: string[11];
begin
 Str(L, S);
 IntToStr := S;
end;

function Init(s : string) : boolean;     {Can I find this file?}
var DirInfo : SearchRec;
begin
     movenum := 0;
     FindFirst(s, Archive, DirInfo);
     if DosError = 0 then Init := true
     else Init := false;
end;

procedure Read15(s:string);               {Reads the file and puts numbers}
var F : text;                             {in MAIN}
    x, y, j : byte;
    c : char;
    num : string;
begin
   Assign(F, s);
   Reset(F);
   num := '';
   for x := 1 to 4 do begin
      for y := 1 to 4 do begin
         if (y=4) and not(Eoln(F)) then begin
            read(F, c);
            num := num + c;
         end else

         if not(Eoln(F)) then begin
         repeat
           read(F, c);
           if c <> ' ' then num := num + c;
         until (c = ' ') or (Eoln(F));

         if num = 'X' then begin
            main[x, y] := 0;
            xX := x; yX := y;
         end else
            main[x, y] := StrToInt(num);
         while (c = ' ') and (not(Eoln(F))) do read(F, c);
         num := '' + c;
         end;

         if y = 4 then begin
            if not Eoln(F) then begin
               read(F, c); num := num + c;
            end;
            main[x, y] := StrToInt(num);
            num := '';
            if Eoln(F) then readln(F);
         end;

      end;
   end;
   Close(F);

end;

function Control : boolean;    {Is it solution?}
begin
if (main[1, 1] = 1) and (main[2, 1] = 2) and (main[3, 1] = 3) and (main[4, 1] = 4) and
   (main[1, 2] = 5) and (main[2, 2] = 6) and (main[3, 2] = 7) and (main[4, 2] = 8) and
   (main[1, 3] = 9) and (main[2, 3] = 10) and (main[3, 3] = 11) and (main[4, 3] = 12) and
   (main[1, 4] = 13) and (main[2, 4] = 14) and (main[3, 4] = 15) then Control := true
else Control := false;
end;

procedure Switch(d : directions); {move with number}
begin
inc(movenum);
moves[movenum] := d;
case d of
  LEFT : begin
           main[xX, yX] := main[xX, yX+1]; inc(yX); main[xX, yX] := 0;
         end;
  RIGHT :begin
           main[xX, yX] := main[xX, yX-1]; dec(yX); main[xX, yX] := 0;
         end;
  UP :   begin
           main[xX, yX] := main[xX+1, yX]; inc(xX); main[xX, yX] := 0;
         end;
  DOWN : begin
           main[xX, yX] := main[xX-1, yX]; dec(xX); main[xX, yX] := 0;
         end;
end;
end;

function allhere : boolean;
var valid : array[0..15] of boolean;       {are all the numbers in input file}
    k, j : byte;
    nothere : boolean;                     {is that number in input file?}
begin
    for k := 0 to 15 do valid[k] := false;
    nothere := false;
    for k := 1 to 4 do
       for j := 1 to 4 do
          valid[main[k, j]] := true;
    for k := 0 to 15 do
        if not valid[k] then nothere:= true;
    allhere := not(nothere);
end;

{find all solutions under DEPTH moves deep (recursion)
 possible ways to increase speed:
 1) better to move number, which has the longest way to its place
    (if they are 2 then the smaller one)
 2) if it is not possible to get closer, then move with number
    which has shortest way to its place
    (if they are 2 then the bigger one)

 ((trying to find heuristic way to speed up))
}
procedure Shift;
begin
  if Control then begin
     writeln(IntToStr(movenum));
     for i := 1 to movenum do
         case moves[i] of
              LEFT : writeln('LEFT');
              RIGHT : writeln('RIGHT');
              UP : writeln('UP');
              DOWN : writeln('DOWN');
         end;
         halt(1);
  end;
  if movenum > Depth then begin
     dec(movenum);
  end else if movenum > 0 then begin
        case moves[movenum] of
           LEFT : begin
                     if yX > 1 then begin
                         switch(DOWN); Shift; end;
                     if yX < 4 then begin
                         switch(UP); Shift; end;
                     if xX < 4 then begin
                         switch(LEFT); Shift; end;
                  end;
           RIGHT : begin
                     if yX > 1 then begin
                         switch(DOWN); Shift; end;
                     if yX < 4 then begin
                         switch(UP); Shift; end;
                     if yX > 1 then begin
                         switch(RIGHT); Shift; end;
                   end;
           UP : begin
                     if xX > 1 then begin
                         switch(RIGHT); Shift; end;
                     if xX < 4 then begin
                         switch(LEFT); Shift; end;
                     if yX < 4 then begin
                         switch(UP); Shift; end;
                  end;
           DOWN : begin
                     if xX > 1 then begin
                         switch(RIGHT); Shift; end;
                     if xX < 4 then begin
                         switch(LEFT); Shift; end;
                     if yX > 1 then begin
                         switch(DOWN); Shift; end;
                  end;
          end;
  end else begin
                     if yX > 1 then begin
                         switch(DOWN); Shift; end;
                     if yX < 4 then begin
                         switch(UP); Shift; end;
                     if xX < 4 then begin
                         switch(LEFT); Shift; end;
                     if xX > 1 then begin
                         switch(RIGHT); Shift; end;
  end;
end;

begin
  ClrScr;
  par := ParamStr(Paramcount); parnum := ParamCount;
  if ParamCount = 0 then
    Writeln('Usage: 18GAME <filename>')
  else begin
    if Init(ParamStr(ParamCount)) then begin
       Read15(ParamStr(ParamCount));
       if allhere then begin
          Shift;
          writeln('No solution possible');
       end else writeln('This input numbers are incorect!!!');
    end else begin
       if par[0] <> '-' then begin
            Writeln('Invalid file name!');
            Writeln('Usage: 18GAME <filename>');
       end else Writeln('Usage: 18GAME <filename>');

    end;
  end;
end.