#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <conio.h>

#define NDEBUG
#define TMPNAME "04game.$$$"

typedef int one;
typedef one fld[4][4];
typedef int RC;

int long total=0;
FILE *outf;

fld a,recode;

char Asolve=0,Ashow=0;

char *Afn1,*Afn2;
int br,bc;

#define LIN(r,c) (((r)*4+(c)+1)%16)
#define R_LIN(l) (((l==0?16:l)-1)/4)
#define C_LIN(l) (((l==0?16:l)-1)%4)

#define EXPANDX(arg) do { arg##r=R_LIN(arg);arg##c=C_LIN(arg); } while(0)
#define EXPANDD(arg) int arg##r,arg##c

static void readfld(fld a,const char *fn)
{
FILE *f;
char s[2000];
int r,c,v;

	f=fopen(fn,"rt"); if (!f) { perror(fn); exit(EXIT_FAILURE); }
	for (r=0;r<4;r++)
		for (c=0;c<4;c++) {
			fscanf(f,"%s",&s);
			v=(!strcmp(s,"X")?0:(int)atol(s));
			a[r][c]=v;
			}

	fclose(f);
}

#ifdef NDEBUG
#define dump(a,b)
#else

static void dump(char *tit,fld a)
{
int r,c;

	printf("%s:\n",tit);
	for (r=0;r<4;r++) {
		printf("  ");
		for (c=0;c<4;c++) {
			printf(" %2u",a[r][c]);
			}
		putchar('\n');
		}
	printf("%s done.\n",tit);
}
#endif

int seekfor(one pc)
{
int r,c;
	printf("seekfor(%d)\n",pc);
	for (r=0;r<4;r++)
		for (c=0;c<4;c++)
			if (a[r][c]==pc) return LIN(r,c);
	assert(0);
	return(0);
}

static int step(int fromr,int fromc,int tor,int toc)
{
	if (fromc<toc) return LIN(fromr,fromc+1);
	if (fromr<tor) return LIN(fromr+1,fromc);
	if (toc<fromc) return LIN(fromr,fromc-1);
	if (tor<fromr) return LIN(fromr-1,fromc);
	return LIN(fromr,fromc);
}

int nors=-1,nore=-1,nocs=-1,noce=-1;

static void toout(char ch)
{
	if (Ashow) {
int r,c,x;
		clrscr();
		for (r=0;r<4;r++) {
			printf("  ");
			for (c=0;c<4;c++) {
				if (a[r][c]) printf(" %2u",a[r][c]);
				else printf("  X");
				}
			putchar('\n');
			}
		puts("Press any key to continue...");
		x=getchar();
		x=x;
		}
	total++;
	if (outf) fputc(ch,outf);
}

static void bmove(int dr,int dc,int nor,int noc)
{
int nbr,nbc;
#ifndef NDEBUG
	printf("BMOVE(%d,%d)",dr,dc);
#endif
	assert(!a[br][bc]);
	assert(br>=0 && br<4 && bc>=0 && bc<4);
	while (dc>bc) {
		nbr=br; nbc=bc+1;
#define CHECKX if ((nbr>=nors && nbr<=nore && nbc>=nocs && nbc<=noce) || (nbr==nor && nbc==noc))
		CHECKX {
			if (br<3) bmove(br+1,bc,nor,noc);
			else bmove(br-1,bc,nor,noc);
			continue;
			}
		a[br][bc]=a[nbr][nbc]; a[nbr][nbc]=0; bc++; toout('L'); }
	while (dc<bc) {
		nbr=br; nbc=bc-1;
		CHECKX {
			if (br<3) bmove(br+1,bc,nor,noc);
			else bmove(br-1,bc,nor,noc);
			continue;
			}
		a[br][bc]=a[nbr][nbc]; a[nbr][nbc]=0; bc--; toout('R'); }
	while (dr>br) {
		nbr=br+1; nbc=bc;
		CHECKX {
			if (bc<3) bmove(br,bc+1,nor,noc);
			else bmove(br,bc-1,nor,noc);
			continue;
			}
		a[br][bc]=a[nbr][nbc]; a[nbr][nbc]=0; br++; toout('U'); }
	while (dr<br) {
		nbr=br-1; nbc=bc;
		CHECKX {
			if (bc<3) bmove(br,bc+1,nor,noc);
			else bmove(br,bc-1,nor,noc);
			continue;
			}
		a[br][bc]=a[nbr][nbc]; a[nbr][nbc]=0; br--; toout('D'); }
	assert(br>=0 && br<4 && bc>=0 && bc<4);
	dump("BMOVE done",a);
}
/*
static int between(int l,int r,int m)
{
	return ((l<r && l<=m && m<=r)
				||(l>r && r<=m && m<=l));
}
*/
static void hardmove(int fromr,int fromc,int tor,int toc)
{
	while (fromr!=tor || fromc!=toc) {
EXPANDD(To);
int To=step(fromr,fromc,tor,toc);
		EXPANDX(To);

#ifndef NDEBUG
printf("from=(%d,%d),to=(%d,%d),To=(%d,%d)\n",
	fromr,fromc,tor,toc,Tor,Toc);
#endif

		bmove(Tor,Toc,fromr,fromc);
		bmove(fromr,fromc,-1,-1);
		fromr=Tor; fromc=Toc;
		}
}

static void hackmode(void)
{
int targ;

	nors=0;nore=0;nocs=0;
	for (targ=0;targ<4;targ++) {
EXPANDD(fs);
int fs=seekfor(targ+1);

		EXPANDX(fs);
		noce=targ-1-(targ==3);
		hardmove(fsr,fsc,0,targ+(targ==2));
		}
	nors=0;nocs=0;noce=0;
	for (targ=1;targ<4;targ++) {
EXPANDD(fs);
int fs=seekfor(targ*4+1);

		EXPANDX(fs);
		nore=targ-1-(targ==3);
		hardmove(fsr,fsc,targ+(targ==2),0);
		}
	nors=0;nore=1;nocs=0;
	for (targ=1;targ<4;targ++) {
EXPANDD(fs);
int fs=seekfor(targ+5);

		EXPANDX(fs);
		noce=targ-1-(targ==3);
		hardmove(fsr,fsc,1,targ+(targ==2));
		}
	bmove(3,3,3,0);
}

#define STMASK (0xFFFFFFUL)
#define HASHSIZE (297UL)
#define FINAL (0xABCEF0UL)

unsigned long totnodes=0;

static unsigned calchash(unsigned long s)
{
	s^=(s<<3U);
	s^=(s>>4U)^(s>>16U);
	return((unsigned)(s%HASHSIZE));
}

struct stnode {
	struct stnode *hnext,*snext,*forw;
	unsigned char howr,howc;
	unsigned long st;
	unsigned long from;
	} *hashtab[HASHSIZE],*slist,**slistp=&slist,*finaln;

static struct stnode *getnode(unsigned long st)
{
unsigned h=calchash(st);
struct stnode *r;
	for (r=hashtab[h];r;r=r->hnext)
		if (r->st==st) break;
	return(r);
}

static struct stnode *addnode(unsigned long st,unsigned long from)
{
struct stnode *n;
unsigned h;

	totnodes++;
	if (getnode(st)) return(NULL);
	n=malloc(sizeof(*n));
	if (!n) {
		printf("FATAL: out of memory after %d nodes of 720 total\n");
		exit(1);
		}
	n->snext=NULL;
	h=calchash(st);
	n->hnext=hashtab[h];
	n->st=st; n->from=from;
	hashtab[h]=n;
	*slistp=n;
	slistp=&n->snext;
	return(n);
}

static int hashmove(unsigned long st,int dr,int dc)
{
one a[2][3];
int r,c,lbr=10,lbc=10;
unsigned long newst;
struct stnode *n;

	for (r=0;r<2;r++)
		for (c=0;c<3;c++) {
			a[r][c]=(unsigned char)((st>>((unsigned)((5-(r*3+c))*4)))&0x0F);
			if (!a[r][c])
				{ lbr=r; lbc=c; }
			}
	assert(lbr>=0 && lbr<2 && lbc>=0 && lbc<3);
	if (lbr+dr<0 || lbr+dr>=2 || lbc+dc<0 || lbc+dc>=3)
		return(0);
	a[lbr][lbc]=a[lbr+dr][lbc+dc];
	a[lbr+dr][lbc+dc]=0;
	newst=0;
	for (r=0;r<2;r++)
		for (c=0;c<3;c++)
			newst=(newst<<4U)|a[r][c];
	if ((n=addnode(newst,st))!=0) {
		n->howr=dr;
		n->howc=dc;
		}
	if (newst==FINAL) {
		assert(n);
		finaln=n;
		return(1);
		}
	return(0);
}

static void searchmode(void)
{
unsigned long start=0;
int r,c;
struct stnode *prevn,*finaln=NULL;

	for (r=2;r<4;r++)
		for (c=1;c<4;c++)
			start=(start<<4U)|a[r][c];
	if (start==FINAL) return;
	addnode(start,start);
	while (slist) {
struct stnode *n;
		n=slist; slist=n->snext;
		if (!slist) slistp=&slist;
		if (hashmove(n->st,+1, 0)) break;
		if (hashmove(n->st,-1, 0)) break;
		if (hashmove(n->st, 0,+1)) break;
		if (hashmove(n->st, 0,-1)) break;
		}
	if (!finaln) {
		printf("NO SOLUTION (%lu nodes)\n",totnodes);
		exit(1);
		}
	prevn=NULL;
	while (finaln) {
		finaln->forw=prevn;
		prevn=finaln;
		if (finaln->from!=finaln->st)
			finaln=getnode(finaln->from);
		else finaln=NULL;
		}
	assert(finaln->from==finaln->st);
	while (finaln) {
		bmove(finaln->howr,finaln->howc,-1,-1);
		finaln=finaln->forw;
		}
/*freeing not needed, algorithm finishes*/
}

static void cleanup(void)
{
	fclose(outf);
	unlink(TMPNAME);
}

int main(int argc,char **argv)
{
int i,r,c;
	puts("***START");
	for (i=1;i<argc;i++) {
		if (!strcmp(argv[i],"-solve")) Asolve=1;
		else if (!strcmp(argv[i],"-show")) Ashow=1;
		else if (!Afn1) Afn1=argv[i];
		else if (!Afn2) Afn2=argv[i];
		}
	if (Afn1) {
		readfld(a,Afn1);
		dump("A",a);
		}
	if (Afn2) {
int r,c;
one from,to,rectab[16];
		for (r=0;r<16;r++) rectab[r]=r;

		readfld(recode,Afn2);
		for (r=0;r<4;r++)
			for (c=0;c<4;c++) {
				from=recode[r][c];
				to=LIN(r,c);
				rectab[from]=to;
				}
		for (r=0;r<4;r++)
			for (c=0;c<4;c++) {
				a[r][c]=rectab[(int)a[r][c]];
				}
		dump("recode",recode);
		dump("A after recode",a);
		}
	br=10; bc=10;
	for (r=0;r<4;r++)
		for (c=0;c<4;c++)
			if (!a[r][c]) { br=r; bc=c;; break; }
	if (br>=10 || bc>=10) { printf("ERROR input\n"); exit(1); }

	if (Asolve) {
		outf=fopen(TMPNAME,"wb+"); assert(!!outf);
		atexit(cleanup);
		}

	hackmode();
	searchmode();

	if (Asolve) {

	fseek(outf,0,SEEK_SET);
	printf("%lu\n",total);
#ifndef NDEBUG
	total=0;
#endif
	while (total--) {
char c;
int i;
		i=fread(&c,1,1,outf); assert(i==1);
		switch (c) {
			case 'L': puts("LEFT" ); break;
			case 'R': puts("RIGHT"); break;
			case 'D': puts("DOWN" ); break;
			case 'U': puts("UP"   ); break;
			default: assert(0);
			}
		}
		}
	else puts("SOLVABLE");
	return(EXIT_SUCCESS);
}