{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+}
{$M 64000,0,655360}
program Contest;
uses Crt;

type    NUMBERS      = 0..15;
        MATRIX       = array[1..4,1..4] of NUMBERS;
        WORDS_TYPE   = (LEFT,RIGHT,UP,DOWN);

var Mat            : MATRIX; {The original matrix}
    Final          : MATRIX; {The final matrix}
    Temp           : MATRIX; {Temporal matrix}
    Switch, P1, P2 : string; {Parameters and switches}
    P              : 0..3;   {Number of parameters or switches}
    Steps          : array[1..100] of WORDS_TYPE;

procedure Read_Final;
{-- This procedure reads the final configuration --}
var F   : Text;
    i,j : integer;
begin
     assign(F, P2);
     reset(F);
      for j:=1 to 4 do
      begin
           for i:=1 to 4 do
                    read(F, Final[i,j]);
           readln(F);
      end;
     close(F);
end;

Procedure Parameters;
{-- Treats the parameters passed to the program --}
begin
     Switch:=''; P1:=''; P2:='';
     P:=ParamCount;
     if P=1 then
          P1:=ParamStr(1);
     if P=2 then
     begin
          Switch:=ParamStr(1);
          P1:=ParamStr(2);
     end;
     if P=3 then
     begin
          Switch:=ParamStr(1);
          P1:=ParamStr(2);
          P2:=ParamStr(3);
          Read_Final;
     end;
end;

procedure Read_Game;
{-- This procedure reads the input file --}
var F   : Text;
    i,j : integer;
begin
     assign(F, P1);
     reset(F);
      for j:=1 to 4 do
      begin
           for i:=1 to 4 do
                    read(F, Mat[i,j]);
           readln(F);
      end;
     close(F);
end;

Function Solution:boolean;
{TRUE if there is a solution}
var i,j   : integer;
    S1,S2 : array[1..4] of byte;
    Check : boolean;
begin
     ClrScr;
     for i:=1 to 4 do
     begin
          S1[i]:=0;
          S2[i]:=0;
     end;
     for j:=1 to 4 do
         for i:=1 to 4 do
             S1[j]:=S1[j]+Mat[i,j];
     for j:=1 to 4 do
         for i:=1 to 4 do
             S2[j]:=S2[j]+Mat[j,i];
     Check:=true;
     for i:=1 to 4 do
         if (S1[i]<>30) or (S2[i]<>30) then
            begin
                 Check:=false;
                 i:=4;
            end;
     if Check then Solution:=false else Solution:=true;
end;

Procedure Is_Solution;
{-- Treats the result of the function solution --}
begin
     if Solution=false then
     begin
          WriteLn('There is no soultion for this configuration!');
          ReadLn;
          Halt;
     end else
     begin
          WriteLn('There are solutions... PLEASE WAIT!...');
          writeln('Press enter to move...');
     end;
end;

Procedure Show(t:matrix);
var i,j:integer;
begin
     clrscr;
     for i:=1 to 4 do
     for j:=1 to 4 do
         begin
              gotoxy(i*3+38,j*3+10);
              if T[i,j]=0 then
              begin
                   highvideo;
                   write(' X  ');
                   Normvideo;
              end
              else write(T[i,j]);
         end;
end;

Procedure Back( temp:matrix; direction:WORDS_TYPE;i,j : integer);
var Ways   : array[1..4] of WORDS_TYPE;
    NrWays : 0..4;
    k:string[1];

Function Distance(k : NUMBERS): NUMBERS;
{Distance of a number to the place where it should be}
var Posi, Posj, SecPosi, SecPosj, m, n  : integer;
begin
     for m:=1 to 4 do
     for n:=1 to 4 do
         if Temp[m,n]=k then
         begin
              Posi:=m;
              Posj:=n;
         end;
     for m:=1 to 4 do
     for n:=1 to 4 do
         if Final[m,n]=k then
         begin
              SecPosi:=m;
              SecPosj:=n;
         end;
     Distance:=(abs((SecPosi-Posi))+abs((SecPosj-Posj)));
end;

Function Ready:boolean;
var o,p : byte;
    b   : boolean;
begin
     b:=true;
     for o:=1 to 4 do
     for p:=1 to 4 do
      if Temp[o,p]<>Final[o,p] then
      begin
           b:=false;
      end;
     Ready:=b;
end;

Procedure Move(a1,b1,a2,b2:integer);
{Switches two numbers on matrix TEMP}
var t : integer;
begin
     Temp[a1,b1]:=Temp[a2,b2];
     Temp[a2,b2]:=0;
end;

Procedure position;
begin
     gotoxy(10,5);
     write(i,',',j,'   ');
end;

Function Already(x : WORDS_TYPE):Boolean;
var l : byte;
    b : boolean;
begin
     b:=false;
     for l:=1 to 4 do
         if Ways[l]=x then
         begin
              b:=true;
              l:=4;
         end;
     Already:=b;
end;

Function In_Range(x,y:integer):Boolean;
begin
     In_Range:=((x>0) and (x<5) and (y>0) and (y<5));
end;

Function Get_Next:WORDS_TYPE;
var way : WORDS_TYPE;
    ok  : boolean;
begin
     ok:=false;
     if (not ok) and (in_range(i-1,j)) and (not already(LEFT)) then
     begin
          ok:=true;
          Get_Next:=LEFT;
     end;
     if (not ok) and (in_range(i+1,j)) and (not already(RIGHT)) then
     begin
          ok:=true;
          Get_Next:=RIGHT;
     end;
     if (not ok) and (in_range(i,j+1)) and (not already(DOWN)) then
     begin
          ok:=true;
          Get_Next:=DOWN;
     end;
     if (not ok) and (in_range(i,j-1)) and (not already(UP)) then
     begin
          ok:=true;
          Get_Next:=UP;
     end;
end;

Function Minim(a,b:integer):WORDS_TYPE;
var x,y,z1,z2,z3,z4,t:integer;
    t2:matrix;
begin
     z1:=0; z2:=0; z3:=0; z4:=0;
     for x:=1 to 4 do
     for y:=1 to 4 do
      t2[x,y]:=temp[x,y];
     t:=t2[a-1,b];
     t2[a-1,b]:=0;
     for x:=1 to 4 do
     for y:=1 to 4 do
      z1:=z1+distance(t2[x,y]);

     for x:=1 to 4 do
     for y:=1 to 4 do
      t2[x,y]:=temp[x,y];
     t:=t2[a+1,b];
     t2[a+1,b]:=0;
     for x:=1 to 4 do
     for y:=1 to 4 do
      z2:=z2+distance(t2[x,y]);

     for x:=1 to 4 do
     for y:=1 to 4 do
      t2[x,y]:=temp[x,y];
     t:=t2[a,b-1];
     t2[a,b-1]:=0;
     for x:=1 to 4 do
     for y:=1 to 4 do
      z3:=z3+distance(t2[x,y]);

     for x:=1 to 4 do
     for y:=1 to 4 do
      t2[x,y]:=temp[x,y];
     t:=t2[a,b+1];
     t2[a,b+1]:=0;
     for x:=1 to 4 do
     for y:=1 to 4 do
      z4:=z4+distance(t2[x,y]);

     t:=z1;
     if z2>t then t:=z2;
     if z3>t then t:=z3;
     if z4>t then t:=z4;
     if t=z1 then minim:=LEFT;
     if t=z2 then minim:=RIGHT;
     if t=z3 then minim:=UP;
     if t=z4 then minim:=DOWN;
end;


{Procedure Back}
begin
     show(temp);
     readln(k);
     if k='q' then halt;
     if ready=false then
     begin
          if {(minim=RIGHT) and }(direction<>RIGHT) and (in_range(i+1,j)) then
          begin
               move(i,j,i+1,j);
               back(temp,LEFT,i+1,j);
          end;
          if {(minim=LEFT) and }(direction<>LEFT) and (in_range(i-1,j)) then
          begin
               move(i,j,i-1,j);
               back(temp,RIGHT,i-1,j);
          end;
          if {(minim=DOWN) and }(direction<>DOWN) and (in_range(i,j+1)) then
          begin
               move(i,j,i,j+1);
               back(temp,UP,i,j+1);
          end;
          if {(minim=UP) and} (direction<>UP) and (in_range(i,j-1)) then
          begin
               move(i,j,i,j-1);
               back(temp,DOWN,i,j-1);
          end;
     end;
end;

Procedure Find_Solution;
var i,j   : integer;
    Count : integer;
begin
     for i:=1 to 4 do
     for j:=1 to 4 do
         Temp[i,j]:=Mat[i,j];
     if P2='' then
     begin
          Count:=0;
          for i:=1 to 4 do
          for j:=1 to 4 do
          begin
               Inc(Count);
               if Count<16 then Final[i,j]:=Count;
          end;
     {* if the final configuration is not introduced then assuming default*}
        Final[4,4]:=0;
     end;
     Show(mat);
     Back(temp,RIGHT,4,4);
end;

{-- MAIN PROGRAM --}
begin
     Parameters;
     Read_Game;
     Is_Solution;
     Find_Solution;
end.