import java.io.*;
import java.util.*;

public class DFS
{

    protected int[][] puzzle;

    public void readFile(String f)
    {
	try
	    {
		BufferedReader bis = new BufferedReader(new FileReader(f));
		for (int i=0; i<puzzle.length; i++)
		    {
			String l = bis.readLine();
			String[] s =l.split(" ");
			int[] jj = new int[s.length];
			puzzle[i]=jj;
			for (int j=0; j<jj.length; j++)
			    jj[j]=Integer.parseInt(s[j]);
		    }
		bis.close();
	    }
	catch (Exception ee)
	    {
		ee.printStackTrace();
	    }
    }


    public int[][] getPuzzle()
    {
	return puzzle;
    }

    public DFS(DFS epc)
    {
	int[][] p = epc.getPuzzle();
	puzzle = new int[p.length][];
	for (int i=0; i<p.length; i++)
	    {
		int[] pp = new int[p[i].length];
		puzzle[i]=pp;
		for (int j=0; j<p[i].length; j++)
		    pp[j]=p[i][j];
	    }
    }

    public String toString()
    {
	StringBuffer sb=new StringBuffer();
	for (int i=0; i<puzzle.length; i++)
	    {
		for (int j=0; j<puzzle[i].length; j++)
		    sb.append(puzzle[i][j]).append(" ");
		sb.append("\n");
	    }
	return sb.toString();
    }

    public Vector legalMoves()
    {
	int spx=-1;
	int spy=-1;
	Vector v = new Vector();
	for (int i=0; i<puzzle.length; i++)
	    for (int j=0; j<puzzle[i].length; j++)
		if (puzzle[i][j]==-1)
		    {
			spx=i;
			spy=j;
			break;
		    }
	//System.out.println(spx + " " + spy);
	if (spy>0)
	    {
		//System.out.println("sawp with " + (spx) + " " + (spy-1));
		DFS ep=new DFS(this);
		ep.swap(spx, spy, spx, spy-1);
		v.add(ep);
	    }
	if (spy<(puzzle[spx].length-1))
	    {
		//System.out.println("sawp with " + (spx) + " " + (spy+1));
		DFS ep=new DFS(this);
		ep.swap(spx, spy, spx, spy+1);
		v.add(ep);
	    }
	if (spx>0)
	    {
		//System.out.println("sawp with " + (spx-1) + " " + (spy));
		DFS ep=new DFS(this);
		ep.swap(spx, spy, spx-1, spy);
		v.add(ep);
	    }
	if (spx<(puzzle.length-1))
	    {
		//System.out.println("sawp with " + (spx+1) + " " + (spy));
		DFS ep=new DFS(this);
		ep.swap(spx, spy, spx+1, spy);
		v.add(ep);
	    }
	return v;
    }

    protected DFS()
    {
    }

    public DFS(int p)
    {
	puzzle = new int[p][];
    }

    public void swap(int spx, int spy, int sx, int sy)
    {
	puzzle[spx][spy]=puzzle[sx][sy];
	puzzle[sx][sy]=-1;
    }

    public boolean isSame(DFS epc)
    {
	int[][] p = epc.getPuzzle();
	boolean gotit=true;
	for (int i=0; i<p.length; i++)
	    for (int j=0; j<p[i].length; j++)
		if (p[i][j]!=puzzle[i][j])
		    return false;
	return true;
}

    public static boolean inList(Object o, List v)
    {
	for (Object oo: v)
	    if (((DFS)o).isSame((DFS)oo))
		{
		    //System.out.println("inlist");
		    return true;
		}
	return false;
    }

    public static void main(String[] s)
    {
	Random r = new Random();
	DFS tee = new DFS(Integer.parseInt(s[2]));
	tee.readFile(s[0]);
	DFS ee = new DFS(Integer.parseInt(s[2]));
	ee.readFile(s[1]);
	Stack openList=new Stack();
	Vector closedList=new Vector();
	System.out.println(ee.toString());
	for (long i=0; i<10000000; i++)
	    {
		Vector legalM = ee.legalMoves();
		for (Object o : legalM)
		    {
			if (((DFS)o).isSame(tee))
			    {
				System.out.println("GOTIT" + i);
				System.exit(1);
			    }
			if (!inList(o, openList) &&
			    !inList(o, closedList))
			    openList.push(o);
		    }
		if (i % 1000 == 1)
		    System.out.println(i + "  " + openList.size() + "  " + (openList.size()/(i*1.0)));
		ee = (DFS) openList.pop();
		closedList.add(ee);
		//System.out.println(ee.toString() + "\n");
	    }
	
    }


}