Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include<stdio.h>
#include<stdlib.h>

int Puzzle[4][4];
int tmp[4][4];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void Empty(int *, int *);
void swap(int *, int *);
int Cal();
int DFS(int, int, int, int, int);

int main(){
  int i, j, l;
  int x, y, a;

for(i=0;i<4;i++)
  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      scanf("%d",&Puzzle[i][j]);
    }
  }

  Empty(&x,&y);

  for(l = 0 ; l < 100 ; l++){
    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 tmp[i][j] = Puzzle[i][j];
      }
    }

    a = DFS(x, y, -1, 0, l);
    if(a != -1){
      printf("%d\n",a);
      break;
    }

    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 Puzzle[i][j] = tmp[i][j];
      }
    }

    a = -1;
    if(l == 99) printf("%d\n",a);
  }

  return 0;
}

void Empty(int *x, int *y){
  int i, j;

  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      if(!Puzzle[i][j]){
 *x = j;
 *y = i;
 return;
      }
    }
  }
}

void swap(int *a, int *b){
  int tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}


int Cal(){
  int i, a;
  int sum = 0;

  for(i = 0 ; i < 16 ; i++){
    a = Puzzle[i/4][i%4];
    if(a){
      a--;
      sum += abs(i/4 - a/4)  + abs(i%4 - a%4);
    }
  }

  return sum;
}

int DFS(int x, int y, int p, int dep, int limit){
  int i, h, nx, ny, res;

  h = Cal();

  if(h == 0) return dep;
  if(dep + h > limit) return -1;

  for(i = 0 ; i < 4 ; i++){
    nx = x + dx[i];
    ny = y + dy[i];

    if(~p && i == (p+2)%4) continue;
    if(!(0 <= nx && nx < 4 && 0 <= ny && ny < 4)) continue;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
    res = DFS(nx, ny, i, dep+1, limit);
    if(~res) return res;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
  }

  return -1;
}


```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	Puzzle
	.bss
	.align 32
	.type	Puzzle, @object
	.size	Puzzle, 64
Puzzle:
	.zero	64
	.globl	tmp
	.align 32
	.type	tmp, @object
	.size	tmp, 64
tmp:
	.zero	64
	.globl	dx
	.data
	.align 16
	.type	dx, @object
	.size	dx, 16
dx:
	.long	0
	.long	1
	.long	0
	.long	-1
	.globl	dy
	.align 16
	.type	dy, @object
	.size	dy, 16
dy:
	.long	1
	.long	0
	.long	-1
	.long	0
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	movl	$0, -24(%rbp)
	jmp	.L2
.L7:
	movl	$0, -24(%rbp)
	jmp	.L3
.L6:
	movl	$0, -20(%rbp)
	jmp	.L4
.L5:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -20(%rbp)
.L4:
	cmpl	$3, -20(%rbp)
	jle	.L5
	addl	$1, -24(%rbp)
.L3:
	cmpl	$3, -24(%rbp)
	jle	.L6
	addl	$1, -24(%rbp)
.L2:
	cmpl	$3, -24(%rbp)
	jle	.L7
	leaq	-28(%rbp), %rdx
	leaq	-32(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	Empty
	movl	$0, -16(%rbp)
	jmp	.L8
.L20:
	movl	$0, -24(%rbp)
	jmp	.L9
.L12:
	movl	$0, -20(%rbp)
	jmp	.L10
.L11:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	tmp(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L10:
	cmpl	$3, -20(%rbp)
	jle	.L11
	addl	$1, -24(%rbp)
.L9:
	cmpl	$3, -24(%rbp)
	jle	.L12
	movl	-28(%rbp), %esi
	movl	-32(%rbp), %eax
	movl	-16(%rbp), %edx
	movl	%edx, %r8d
	movl	$0, %ecx
	movl	$-1, %edx
	movl	%eax, %edi
	call	DFS
	movl	%eax, -12(%rbp)
	cmpl	$-1, -12(%rbp)
	je	.L13
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L14
.L13:
	movl	$0, -24(%rbp)
	jmp	.L15
.L18:
	movl	$0, -20(%rbp)
	jmp	.L16
.L17:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	tmp(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	Puzzle(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L16:
	cmpl	$3, -20(%rbp)
	jle	.L17
	addl	$1, -24(%rbp)
.L15:
	cmpl	$3, -24(%rbp)
	jle	.L18
	movl	$-1, -12(%rbp)
	cmpl	$99, -16(%rbp)
	jne	.L19
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L19:
	addl	$1, -16(%rbp)
.L8:
	cmpl	$99, -16(%rbp)
	jle	.L20
.L14:
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L22
	call	__stack_chk_fail@PLT
.L22:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	main, .-main
	.globl	Empty
	.type	Empty, @function
Empty:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L24
.L29:
	movl	$0, -4(%rbp)
	jmp	.L25
.L28:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L26
	movq	-24(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-8(%rbp), %edx
	movl	%edx, (%rax)
	jmp	.L23
.L26:
	addl	$1, -4(%rbp)
.L25:
	cmpl	$3, -4(%rbp)
	jle	.L28
	addl	$1, -8(%rbp)
.L24:
	cmpl	$3, -8(%rbp)
	jle	.L29
.L23:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	Empty, .-Empty
	.globl	swap
	.type	swap, @function
swap:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movq	-24(%rbp), %rax
	movl	(%rax), %eax
	movl	%eax, -4(%rbp)
	movq	-32(%rbp), %rax
	movl	(%rax), %edx
	movq	-24(%rbp), %rax
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	swap, .-swap
	.globl	Cal
	.type	Cal, @function
Cal:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	$0, -8(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L32
.L34:
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movslq	%eax, %rdx
	movslq	%ecx, %rax
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	cmpl	$0, -4(%rbp)
	je	.L33
	subl	$1, -4(%rbp)
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-4(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	%ecx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %esi
	movl	-4(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	movl	%esi, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	addl	%ecx, %eax
	addl	%eax, -8(%rbp)
.L33:
	addl	$1, -12(%rbp)
.L32:
	cmpl	$15, -12(%rbp)
	jle	.L34
	movl	-8(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	Cal, .-Cal
	.globl	DFS
	.type	DFS, @function
DFS:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movl	%edi, -36(%rbp)
	movl	%esi, -40(%rbp)
	movl	%edx, -44(%rbp)
	movl	%ecx, -48(%rbp)
	movl	%r8d, -52(%rbp)
	movl	$0, %eax
	call	Cal
	movl	%eax, -16(%rbp)
	cmpl	$0, -16(%rbp)
	jne	.L37
	movl	-48(%rbp), %eax
	jmp	.L38
.L37:
	movl	-48(%rbp), %edx
	movl	-16(%rbp), %eax
	addl	%edx, %eax
	cmpl	%eax, -52(%rbp)
	jge	.L39
	movl	$-1, %eax
	jmp	.L38
.L39:
	movl	$0, -20(%rbp)
	jmp	.L40
.L46:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dx(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-36(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -12(%rbp)
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dy(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-40(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -8(%rbp)
	cmpl	$-1, -44(%rbp)
	je	.L41
	movl	-44(%rbp), %eax
	addl	$2, %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	cmpl	%eax, -20(%rbp)
	je	.L47
.L41:
	cmpl	$0, -12(%rbp)
	js	.L48
	cmpl	$3, -12(%rbp)
	jg	.L48
	cmpl	$0, -8(%rbp)
	js	.L48
	cmpl	$3, -8(%rbp)
	jg	.L48
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	movl	-48(%rbp), %eax
	leal	1(%rax), %ecx
	movl	-52(%rbp), %edi
	movl	-20(%rbp), %edx
	movl	-8(%rbp), %esi
	movl	-12(%rbp), %eax
	movl	%edi, %r8d
	movl	%eax, %edi
	call	DFS
	movl	%eax, -4(%rbp)
	cmpl	$-1, -4(%rbp)
	je	.L45
	movl	-4(%rbp), %eax
	jmp	.L38
.L45:
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	jmp	.L42
.L47:
	nop
	jmp	.L42
.L48:
	nop
.L42:
	addl	$1, -20(%rbp)
.L40:
	cmpl	$3, -20(%rbp)
	jle	.L46
	movl	$-1, %eax
.L38:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	DFS, .-DFS
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
user
	.file	"temp.c"
	.text
	.p2align 4
	.type	DFS.part.0, @function
DFS.part.0:
.LFB44:
	.cfi_startproc
	leal	2(%rdx), %eax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	movl	%esi, %r14d
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movl	%edx, %r13d
	cltd
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	shrl	$30, %edx
	movl	%edi, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	addl	%edx, %eax
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	andl	$3, %eax
	xorl	%ebx, %ebx
	subl	%edx, %eax
	movslq	%esi, %rdx
	subq	$56, %rsp
	.cfi_def_cfa_offset 112
	movl	%eax, 12(%rsp)
	movslq	%edi, %rax
	leaq	(%rax,%rdx,4), %rax
	movl	%ecx, 40(%rsp)
	movl	%r8d, 44(%rsp)
	movq	%rax, 16(%rsp)
.L23:
	leaq	dx(%rip), %rax
	movl	%ebx, %r9d
	movl	(%rax,%rbx,4), %edi
	leaq	dy(%rip), %rax
	movl	(%rax,%rbx,4), %esi
	addl	%r12d, %edi
	addl	%r14d, %esi
	cmpl	$-1, %r13d
	je	.L2
	cmpl	%ebx, 12(%rsp)
	je	.L3
.L2:
	movl	%edi, %eax
	orl	%esi, %eax
	cmpl	$3, %eax
	jbe	.L82
.L3:
	addq	$1, %rbx
	cmpq	$4, %rbx
	jne	.L23
	movl	$-1, %ecx
.L1:
	addq	$56, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movl	%ecx, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L82:
	.cfi_restore_state
	movq	16(%rsp), %rcx
	movslq	%esi, %rdx
	movslq	%edi, %rax
	leaq	Puzzle(%rip), %rbp
	movq	%rax, 24(%rsp)
	leaq	(%rax,%rdx,4), %rax
	movl	0(%rbp,%rcx,4), %r10d
	movq	%rdx, 32(%rsp)
	movl	0(%rbp,%rax,4), %edx
	movl	%edx, 0(%rbp,%rcx,4)
	movl	%r10d, 0(%rbp,%rax,4)
	movl	40(%rsp), %eax
	leal	1(%rax), %ecx
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L4
	leal	2(%rax), %edx
	subl	$1, %eax
	cmovns	%eax, %edx
	sarl	$2, %edx
	movl	%edx, %r8d
	negl	%r8d
	cmovs	%edx, %r8d
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	leal	(%r8,%rdx), %eax
.L4:
	movl	4+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L5
	leal	-1(%rdx), %r11d
	movl	%r11d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	(%r11,%r8), %r15d
	andl	$3, %r15d
	subl	%r15d, %r8d
	addl	$1, %r8d
	movl	%r8d, %r15d
	negl	%r15d
	cmovns	%r15d, %r8d
	addl	$2, %edx
	testl	%r11d, %r11d
	cmovns	%r11d, %edx
	sarl	$2, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L5:
	movl	8+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L6
	leal	-1(%rdx), %r11d
	movl	%r11d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	(%r11,%r8), %r15d
	andl	$3, %r15d
	subl	%r15d, %r8d
	addl	$2, %r8d
	movl	%r8d, %r15d
	negl	%r15d
	cmovns	%r15d, %r8d
	addl	$2, %edx
	testl	%r11d, %r11d
	cmovns	%r11d, %edx
	sarl	$2, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L6:
	movl	12+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L7
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L7:
	movl	16+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L8
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$1, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L8:
	movl	20+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L9
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L9:
	movl	24+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L10
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L10:
	movl	28+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L11
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L11:
	movl	32+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L12
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$2, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L12:
	movl	36+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L13
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L13:
	movl	40+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L14
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L14:
	movl	44+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L15
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L15:
	movl	48+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L16
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$3, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L16:
	movl	52+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L17
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L17:
	movl	56+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L18
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L18:
	movl	60+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L19
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L19:
	testl	%eax, %eax
	je	.L20
	movl	44(%rsp), %r8d
	addl	%ecx, %eax
	cmpl	%eax, %r8d
	jl	.L21
	movl	%r9d, %edx
	call	DFS.part.0
	movl	%eax, %ecx
.L20:
	cmpl	$-1, %ecx
	jne	.L1
	movq	24(%rsp), %rax
	movq	32(%rsp), %rcx
	leaq	(%rax,%rcx,4), %rax
	movl	0(%rbp,%rax,4), %r10d
.L21:
	movq	16(%rsp), %rax
	movq	32(%rsp), %rcx
	movl	0(%rbp,%rax,4), %edx
	movl	%r10d, 0(%rbp,%rax,4)
	movq	24(%rsp), %rax
	leaq	(%rax,%rcx,4), %rax
	movl	%edx, 0(%rbp,%rax,4)
	jmp	.L3
	.cfi_endproc
.LFE44:
	.size	DFS.part.0, .-DFS.part.0
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB39:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	xorl	%r13d, %r13d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	leaq	.LC0(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	leaq	16+Puzzle(%rip), %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
.L84:
	leaq	-16(%rbp), %rbx
.L85:
	movq	%rbx, %rsi
	movq	%r12, %rdi
	xorl	%eax, %eax
	addq	$4, %rbx
	call	__isoc99_scanf@PLT
	cmpq	%rbx, %rbp
	jne	.L85
	addq	$4, %r13
	addq	$16, %rbp
	cmpq	$16, %r13
	jne	.L84
	movl	Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L118
	movl	4+Puzzle(%rip), %ecx
	movl	8+Puzzle(%rip), %eax
	movl	12+Puzzle(%rip), %esi
	movl	%ecx, 24(%rsp)
	testl	%ecx, %ecx
	je	.L87
	movl	%eax, 24(%rsp)
	movl	12+Puzzle(%rip), %esi
	testl	%eax, %eax
	je	.L88
	movl	%esi, 24(%rsp)
	testl	%esi, %esi
	je	.L89
	movl	16+Puzzle(%rip), %ebx
	testl	%ebx, %ebx
	je	.L119
	movl	20+Puzzle(%rip), %r11d
	testl	%r11d, %r11d
	je	.L120
	movl	24+Puzzle(%rip), %r10d
	testl	%r10d, %r10d
	je	.L121
	movl	28+Puzzle(%rip), %r9d
	testl	%r9d, %r9d
	je	.L122
	movl	32+Puzzle(%rip), %r8d
	testl	%r8d, %r8d
	je	.L123
	movl	36+Puzzle(%rip), %edi
	testl	%edi, %edi
	je	.L124
	cmpl	$0, 40+Puzzle(%rip)
	je	.L125
	cmpl	$0, 44+Puzzle(%rip)
	je	.L126
	cmpl	$0, 48+Puzzle(%rip)
	je	.L193
	cmpl	$0, 52+Puzzle(%rip)
	je	.L194
	cmpl	$0, 56+Puzzle(%rip)
	je	.L195
	cmpl	$0, 60+Puzzle(%rip)
	je	.L196
.L91:
	movd	%esi, %xmm5
	movd	%ecx, %xmm6
	movd	%eax, %xmm1
	xorl	%ebp, %ebp
	movd	%edx, %xmm0
	punpckldq	%xmm5, %xmm1
	movd	28+Puzzle(%rip), %xmm7
	movd	20+Puzzle(%rip), %xmm5
	punpckldq	%xmm6, %xmm0
	movd	16+Puzzle(%rip), %xmm3
	movd	44+Puzzle(%rip), %xmm6
	punpcklqdq	%xmm1, %xmm0
	movd	24+Puzzle(%rip), %xmm1
	movd	32+Puzzle(%rip), %xmm2
	punpckldq	%xmm5, %xmm3
	movd	56+Puzzle(%rip), %xmm4
	movd	60+Puzzle(%rip), %xmm5
	punpckldq	%xmm7, %xmm1
	movd	36+Puzzle(%rip), %xmm7
	punpcklqdq	%xmm1, %xmm3
	movd	40+Puzzle(%rip), %xmm1
	punpckldq	%xmm5, %xmm4
	punpckldq	%xmm7, %xmm2
	punpckldq	%xmm6, %xmm1
	movd	52+Puzzle(%rip), %xmm6
	punpcklqdq	%xmm1, %xmm2
	movd	48+Puzzle(%rip), %xmm1
	punpckldq	%xmm6, %xmm1
	punpcklqdq	%xmm4, %xmm1
	jmp	.L94
	.p2align 4,,10
	.p2align 3
.L198:
	cmpl	%r10d, %ebp
	jl	.L114
	movl	24(%rsp), %esi
	movl	28(%rsp), %edi
	movl	%ebp, %r8d
	xorl	%ecx, %ecx
	movl	$-1, %edx
	call	DFS.part.0
	movl	%eax, %r10d
	cmpl	$-1, %eax
	jne	.L110
.L114:
	leaq	tmp(%rip), %rax
	movdqa	16+tmp(%rip), %xmm3
	movdqa	32+tmp(%rip), %xmm2
	movdqa	(%rax), %xmm0
	movdqa	48+tmp(%rip), %xmm1
	movaps	%xmm3, 16+Puzzle(%rip)
	movaps	%xmm0, Puzzle(%rip)
	movaps	%xmm2, 32+Puzzle(%rip)
	movaps	%xmm1, 48+Puzzle(%rip)
	cmpl	$99, %ebp
	je	.L197
	addl	$1, %ebp
.L94:
	pshufd	$255, %xmm1, %xmm4
	leaq	tmp(%rip), %r15
	movd	%xmm0, %r10d
	movd	%xmm2, 8(%rsp)
	movd	%xmm4, %ebx
	movdqa	%xmm1, %xmm4
	movd	%xmm3, %esi
	movaps	%xmm0, (%r15)
	punpckhdq	%xmm1, %xmm4
	movd	%xmm1, %r9d
	movaps	%xmm3, 16+tmp(%rip)
	movd	%xmm4, %r11d
	pshufd	$85, %xmm1, %xmm4
	movaps	%xmm2, 32+tmp(%rip)
	movd	%xmm4, %edx
	pshufd	$255, %xmm2, %xmm4
	movaps	%xmm1, 48+tmp(%rip)
	movd	%xmm4, 20(%rsp)
	movdqa	%xmm2, %xmm4
	punpckhdq	%xmm2, %xmm4
	movd	%xmm4, 16(%rsp)
	pshufd	$85, %xmm2, %xmm4
	movd	%xmm4, 12(%rsp)
	pshufd	$255, %xmm3, %xmm4
	movd	%xmm4, 4(%rsp)
	movdqa	%xmm3, %xmm4
	punpckhdq	%xmm3, %xmm4
	movd	%xmm4, %edi
	pshufd	$85, %xmm3, %xmm4
	movd	%xmm4, %eax
	pshufd	$255, %xmm0, %xmm4
	movd	%xmm4, %ecx
	movdqa	%xmm0, %xmm4
	punpckhdq	%xmm0, %xmm4
	movd	%xmm4, %r12d
	pshufd	$85, %xmm0, %xmm4
	movd	%xmm4, %r8d
	testl	%r10d, %r10d
	je	.L117
	leal	2(%r10), %r13d
	subl	$1, %r10d
	cmovns	%r10d, %r13d
	sarl	$2, %r13d
	movl	%r13d, %r14d
	negl	%r14d
	cmovs	%r13d, %r14d
	movl	%r10d, %r13d
	sarl	$31, %r13d
	shrl	$30, %r13d
	addl	%r13d, %r10d
	andl	$3, %r10d
	subl	%r13d, %r10d
	movl	%r10d, %r13d
	negl	%r13d
	cmovs	%r10d, %r13d
	leal	(%r14,%r13), %r10d
.L117:
	testl	%r8d, %r8d
	je	.L95
	leal	-1(%r8), %r14d
	movl	%r14d, %r15d
	sarl	$31, %r15d
	shrl	$30, %r15d
	leal	(%r14,%r15), %r13d
	andl	$3, %r13d
	subl	%r15d, %r13d
	movl	$1, %r15d
	subl	%r13d, %r15d
	movl	%r15d, %r13d
	negl	%r13d
	cmovs	%r15d, %r13d
	addl	$2, %r8d
	testl	%r14d, %r14d
	cmovns	%r14d, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r14d
	negl	%r14d
	cmovs	%r8d, %r14d
	addl	%r14d, %r13d
	addl	%r13d, %r10d
.L95:
	testl	%r12d, %r12d
	je	.L96
	leal	-1(%r12), %r13d
	movl	%r13d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	0(%r13,%r8), %r14d
	andl	$3, %r14d
	subl	%r14d, %r8d
	addl	$2, %r8d
	movl	%r8d, %r14d
	negl	%r14d
	cmovns	%r14d, %r8d
	addl	$2, %r12d
	testl	%r13d, %r13d
	cmovns	%r13d, %r12d
	sarl	$2, %r12d
	movl	%r12d, %r13d
	negl	%r13d
	cmovs	%r12d, %r13d
	addl	%r13d, %r8d
	addl	%r8d, %r10d
.L96:
	testl	%ecx, %ecx
	je	.L97
	leal	2(%rcx), %r8d
	subl	$1, %ecx
	cmovns	%ecx, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r12d
	negl	%r12d
	cmovs	%r8d, %r12d
	movl	%ecx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %ecx
	andl	$3, %ecx
	subl	%ecx, %r8d
	leal	3(%r12,%r8), %ecx
	addl	%ecx, %r10d
.L97:
	testl	%esi, %esi
	je	.L98
	leal	2(%rsi), %ecx
	subl	$1, %esi
	cmovns	%esi, %ecx
	movl	%esi, %r12d
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r8d
	negl	%r8d
	cmovs	%ecx, %r8d
	sarl	$31, %r12d
	shrl	$30, %r12d
	leal	(%rsi,%r12), %ecx
	andl	$3, %ecx
	subl	%r12d, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	addl	%esi, %r8d
	addl	%r8d, %r10d
.L98:
	testl	%eax, %eax
	je	.L99
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%eax, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %eax
	andl	$3, %eax
	subl	%esi, %eax
	movl	$1, %esi
	subl	%eax, %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L99:
	testl	%edi, %edi
	je	.L100
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$1, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovs	%eax, %ecx
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %edi
	andl	$3, %edi
	subl	%edi, %eax
	leal	2(%rax), %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L100:
	movl	4(%rsp), %edi
	testl	%edi, %edi
	je	.L101
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$1, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	3(%rsi,%rax), %eax
	addl	%eax, %r10d
.L101:
	movl	8(%rsp), %eax
	testl	%eax, %eax
	je	.L102
	leal	2(%rax), %esi
	subl	$1, %eax
	cmovns	%eax, %esi
	sarl	$2, %esi
	negl	%esi
	addl	$2, %esi
	movl	%esi, %ecx
	negl	%ecx
	cmovs	%esi, %ecx
	movl	%eax, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %eax
	andl	$3, %eax
	subl	%esi, %eax
	movl	%eax, %esi
	negl	%esi
	cmovns	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L102:
	movl	12(%rsp), %edi
	testl	%edi, %edi
	je	.L103
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovns	%esi, %eax
	movl	%edi, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %ecx
	andl	$3, %ecx
	subl	%esi, %ecx
	movl	$1, %esi
	subl	%ecx, %esi
	movl	%esi, %ecx
	negl	%ecx
	cmovs	%esi, %ecx
	addl	%ecx, %eax
	addl	%eax, %r10d
.L103:
	movl	16(%rsp), %edi
	testl	%edi, %edi
	je	.L104
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	2(%rax), %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%eax, %esi
	addl	%esi, %r10d
.L104:
	movl	20(%rsp), %edi
	testl	%edi, %edi
	je	.L105
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	3(%rsi,%rax), %eax
	addl	%eax, %r10d
.L105:
	testl	%r9d, %r9d
	je	.L106
	leal	2(%r9), %eax
	subl	$1, %r9d
	cmovns	%r9d, %eax
	movl	%r9d, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r9,%rcx), %eax
	andl	$3, %eax
	subl	%ecx, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovns	%ecx, %eax
	addl	%esi, %eax
	addl	%eax, %r10d
.L106:
	testl	%edx, %edx
	je	.L107
	leal	2(%rdx), %eax
	subl	$1, %edx
	movl	$1, %esi
	cmovns	%edx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovs	%eax, %ecx
	movl	%edx, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %edx
	andl	$3, %edx
	subl	%eax, %edx
	subl	%edx, %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%ecx, %eax
	addl	%eax, %r10d
.L107:
	testl	%r11d, %r11d
	je	.L108
	leal	2(%r11), %eax
	subl	$1, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	movl	%r11d, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %r11d
	andl	$3, %r11d
	subl	%r11d, %eax
	leal	2(%rax), %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%edx, %eax
	addl	%eax, %r10d
.L108:
	testl	%ebx, %ebx
	je	.L109
	leal	2(%rbx), %eax
	subl	$1, %ebx
	cmovns	%ebx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	movl	%ebx, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ebx
	andl	$3, %ebx
	subl	%ebx, %eax
	leal	3(%rdx,%rax), %eax
	addl	%eax, %r10d
.L109:
	testl	%r10d, %r10d
	jne	.L198
.L110:
	movl	%r10d, %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L115:
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
.L197:
	.cfi_restore_state
	movl	$-1, %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L115
.L120:
	movl	$1, 24(%rsp)
.L87:
	movl	$1, 28(%rsp)
	jmp	.L91
.L121:
	movl	$1, 24(%rsp)
.L88:
	movl	$2, 28(%rsp)
	jmp	.L91
.L122:
	movl	$1, 24(%rsp)
.L89:
	movl	$3, 28(%rsp)
	jmp	.L91
.L118:
	movl	$0, 24(%rsp)
	movl	4+Puzzle(%rip), %ecx
	movl	8+Puzzle(%rip), %eax
	movl	12+Puzzle(%rip), %esi
.L86:
	movl	$0, 28(%rsp)
	jmp	.L91
.L196:
	movl	$3, 24(%rsp)
	jmp	.L89
.L195:
	movl	$3, 24(%rsp)
	jmp	.L88
.L194:
	movl	$3, 24(%rsp)
	jmp	.L87
.L193:
	movl	$3, 24(%rsp)
	jmp	.L86
.L126:
	movl	$2, 24(%rsp)
	jmp	.L89
.L125:
	movl	$2, 24(%rsp)
	jmp	.L88
.L124:
	movl	$2, 24(%rsp)
	jmp	.L87
.L123:
	movl	$2, 24(%rsp)
	jmp	.L86
.L119:
	movl	$1, 24(%rsp)
	jmp	.L86
	.cfi_endproc
.LFE39:
	.size	main, .-main
	.text
	.p2align 4
	.globl	Empty
	.type	Empty, @function
Empty:
.LFB40:
	.cfi_startproc
	endbr64
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L200
	movl	4+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L201
	movl	8+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L202
	movl	12+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L203
	movl	16+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L209
	movl	20+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L210
	movl	24+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L211
	movl	28+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L212
	movl	32+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L213
	movl	36+Puzzle(%rip), %r11d
	testl	%r11d, %r11d
	je	.L214
	movl	40+Puzzle(%rip), %r10d
	testl	%r10d, %r10d
	je	.L215
	movl	44+Puzzle(%rip), %r9d
	testl	%r9d, %r9d
	je	.L216
	movl	48+Puzzle(%rip), %r8d
	movl	$3, %eax
	testl	%r8d, %r8d
	je	.L200
	movl	52+Puzzle(%rip), %ecx
	movl	$3, %eax
	testl	%ecx, %ecx
	je	.L201
	movl	56+Puzzle(%rip), %edx
	movl	$3, %eax
	testl	%edx, %edx
	je	.L202
	movl	60+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L229
	ret
.L209:
	movl	$1, %eax
.L200:
	xorl	%edx, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L210:
	movl	$1, %eax
.L201:
	movl	$1, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L211:
	movl	$1, %eax
.L202:
	movl	$2, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L212:
	movl	$1, %eax
.L203:
	movl	$3, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L229:
	movl	$3, %eax
	jmp	.L203
.L213:
	movl	$2, %eax
	jmp	.L200
.L214:
	movl	$2, %eax
	jmp	.L201
.L215:
	movl	$2, %eax
	jmp	.L202
.L216:
	movl	$2, %eax
	jmp	.L203
	.cfi_endproc
.LFE40:
	.size	Empty, .-Empty
	.p2align 4
	.globl	swap
	.type	swap, @function
swap:
.LFB41:
	.cfi_startproc
	endbr64
	movl	(%rdi), %eax
	movl	(%rsi), %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
	.cfi_endproc
.LFE41:
	.size	swap, .-swap
	.p2align 4
	.globl	Cal
	.type	Cal, @function
Cal:
.LFB42:
	.cfi_startproc
	endbr64
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L232
	leal	2(%rax), %edx
	subl	$1, %eax
	cmovns	%eax, %edx
	sarl	$2, %edx
	movl	%edx, %ecx
	negl	%ecx
	cmovs	%edx, %ecx
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	addl	%ecx, %eax
.L232:
	movl	4+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L233
	leal	-1(%rdx), %esi
	movl	%esi, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rsi,%rcx), %edi
	andl	$3, %edi
	subl	%edi, %ecx
	leal	1(%rcx), %edi
	movl	%edi, %ecx
	negl	%ecx
	cmovs	%edi, %ecx
	addl	$2, %edx
	testl	%esi, %esi
	cmovns	%esi, %edx
	sarl	$2, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L233:
	movl	8+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L234
	leal	-1(%rdx), %esi
	movl	%esi, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rsi,%rcx), %edi
	andl	$3, %edi
	subl	%edi, %ecx
	leal	2(%rcx), %edi
	movl	%edi, %ecx
	negl	%ecx
	cmovs	%edi, %ecx
	addl	$2, %edx
	testl	%esi, %esi
	cmovns	%esi, %edx
	sarl	$2, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L234:
	movl	12+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L235
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L235:
	movl	16+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L236
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L236:
	movl	20+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L237
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L237:
	movl	24+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L238
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L238:
	movl	28+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L239
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L239:
	movl	32+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L240
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L240:
	movl	36+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L241
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L241:
	movl	40+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L242
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L242:
	movl	44+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L243
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L243:
	movl	48+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L244
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L244:
	movl	52+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L245
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L245:
	movl	56+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L246
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L246:
	movl	60+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L231
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L231:
	ret
	.cfi_endproc
.LFE42:
	.size	Cal, .-Cal
	.p2align 4
	.globl	DFS
	.type	DFS, @function
DFS:
.LFB43:
	.cfi_startproc
	endbr64
	movl	%edx, %r9d
	movl	Puzzle(%rip), %edx
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movl	%ecx, %r10d
	testl	%edx, %edx
	je	.L297
	leal	2(%rdx), %eax
	subl	$1, %edx
	cmovns	%edx, %eax
	movl	%edx, %ecx
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovs	%eax, %r11d
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rdx,%rcx), %eax
	andl	$3, %eax
	subl	%ecx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	leal	(%r11,%rax), %edx
.L297:
	movl	4+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L298
	leal	-1(%rax), %r11d
	movl	%r11d, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r11,%rcx), %ebx
	andl	$3, %ebx
	subl	%ebx, %ecx
	leal	1(%rcx), %ebx
	movl	%ebx, %ecx
	negl	%ecx
	cmovs	%ebx, %ecx
	addl	$2, %eax
	testl	%r11d, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L298:
	movl	8+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L299
	leal	-1(%rax), %r11d
	movl	%r11d, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r11,%rcx), %ebx
	andl	$3, %ebx
	subl	%ebx, %ecx
	leal	2(%rcx), %ebx
	movl	%ebx, %ecx
	negl	%ecx
	cmovs	%ebx, %ecx
	addl	$2, %eax
	testl	%r11d, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L299:
	movl	12+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L300
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L300:
	movl	16+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L301
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	movl	%eax, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %eax
	andl	$3, %eax
	subl	%r11d, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L301:
	movl	20+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L302
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L302:
	movl	24+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L303
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L303:
	movl	28+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L304
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L304:
	movl	32+Puzzle(%rip), %ecx
	testl	%ecx, %ecx
	je	.L305
	leal	2(%rcx), %eax
	subl	$1, %ecx
	cmovns	%ecx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	movl	%ecx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %ecx
	andl	$3, %ecx
	subl	%r11d, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	addl	%ecx, %eax
	addl	%eax, %edx
.L305:
	movl	36+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L306
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L306:
	movl	40+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L307
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L307:
	movl	44+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L308
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L308:
	movl	48+Puzzle(%rip), %ecx
	testl	%ecx, %ecx
	je	.L309
	leal	2(%rcx), %eax
	subl	$1, %ecx
	cmovns	%ecx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	movl	%ecx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %ecx
	andl	$3, %ecx
	subl	%r11d, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	addl	%ecx, %eax
	addl	%eax, %edx
.L309:
	movl	52+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L310
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L310:
	movl	56+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L311
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L311:
	movl	60+Puzzle(%rip), %eax
	testl	%eax, %eax
	jne	.L365
	testl	%edx, %edx
	je	.L314
.L366:
	addl	%r10d, %edx
	cmpl	%r8d, %edx
	jg	.L315
	movl	%r10d, %ecx
	movl	%r9d, %edx
	popq	%rbx
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	jmp	DFS.part.0
	.p2align 4,,10
	.p2align 3
.L365:
	.cfi_restore_state
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
	testl	%edx, %edx
	jne	.L366
.L314:
	movl	%r10d, %eax
	popq	%rbx
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
.L315:
	.cfi_restore_state
	movl	$-1, %eax
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE43:
	.size	DFS, .-DFS
	.globl	dy
	.data
	.align 16
	.type	dy, @object
	.size	dy, 16
dy:
	.long	1
	.long	0
	.long	-1
	.long	0
	.globl	dx
	.align 16
	.type	dx, @object
	.size	dx, 16
dx:
	.long	0
	.long	1
	.long	0
	.long	-1
	.globl	tmp
	.bss
	.align 32
	.type	tmp, @object
	.size	tmp, 64
tmp:
	.zero	64
	.globl	Puzzle
	.align 32
	.type	Puzzle, @object
	.size	Puzzle, 64
Puzzle:
	.zero	64
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

rule
	.file	"temp.c"
	.text
	.p2align 4
	.type	DFS.part.0, @function
DFS.part.0:
.LFB44:
	.cfi_startproc
	leal	2(%rdx), %eax
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	movl	%esi, %r14d
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	movl	%edx, %r13d
	cltd
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	shrl	$30, %edx
	movl	%edi, %r12d
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	addl	%edx, %eax
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	andl	$3, %eax
	xorl	%ebx, %ebx
	subl	%edx, %eax
	movslq	%esi, %rdx
	subq	$56, %rsp
	.cfi_def_cfa_offset 112
	movl	%eax, 12(%rsp)
	movslq	%edi, %rax
	leaq	(%rax,%rdx,4), %rax
	movl	%ecx, 40(%rsp)
	movl	%r8d, 44(%rsp)
	movq	%rax, 16(%rsp)
.L23:
	leaq	dx(%rip), %rax
	movl	%ebx, %r9d
	movl	(%rax,%rbx,4), %edi
	leaq	dy(%rip), %rax
	movl	(%rax,%rbx,4), %esi
	addl	%r12d, %edi
	addl	%r14d, %esi
	cmpl	$-1, %r13d
	je	.L2
	cmpl	%ebx, 12(%rsp)
	je	.L3
.L2:
	movl	%edi, %eax
	orl	%esi, %eax
	cmpl	$3, %eax
	jbe	.L82
.L3:
	addq	$1, %rbx
	cmpq	$4, %rbx
	jne	.L23
	movl	$-1, %ecx
.L1:
	addq	$56, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	movl	%ecx, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
	.p2align 4,,10
	.p2align 3
.L82:
	.cfi_restore_state
	movq	16(%rsp), %rcx
	movslq	%esi, %rdx
	movslq	%edi, %rax
	leaq	Puzzle(%rip), %rbp
	movq	%rax, 24(%rsp)
	leaq	(%rax,%rdx,4), %rax
	movl	0(%rbp,%rcx,4), %r10d
	movq	%rdx, 32(%rsp)
	movl	0(%rbp,%rax,4), %edx
	movl	%edx, 0(%rbp,%rcx,4)
	movl	%r10d, 0(%rbp,%rax,4)
	movl	40(%rsp), %eax
	leal	1(%rax), %ecx
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L4
	leal	2(%rax), %edx
	subl	$1, %eax
	cmovns	%eax, %edx
	sarl	$2, %edx
	movl	%edx, %r8d
	negl	%r8d
	cmovs	%edx, %r8d
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	leal	(%r8,%rdx), %eax
.L4:
	movl	4+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L5
	leal	-1(%rdx), %r11d
	movl	%r11d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	(%r11,%r8), %r15d
	andl	$3, %r15d
	subl	%r15d, %r8d
	addl	$1, %r8d
	movl	%r8d, %r15d
	negl	%r15d
	cmovns	%r15d, %r8d
	addl	$2, %edx
	testl	%r11d, %r11d
	cmovns	%r11d, %edx
	sarl	$2, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L5:
	movl	8+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L6
	leal	-1(%rdx), %r11d
	movl	%r11d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	(%r11,%r8), %r15d
	andl	$3, %r15d
	subl	%r15d, %r8d
	addl	$2, %r8d
	movl	%r8d, %r15d
	negl	%r15d
	cmovns	%r15d, %r8d
	addl	$2, %edx
	testl	%r11d, %r11d
	cmovns	%r11d, %edx
	sarl	$2, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L6:
	movl	12+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L7
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L7:
	movl	16+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L8
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$1, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L8:
	movl	20+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L9
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L9:
	movl	24+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L10
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L10:
	movl	28+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L11
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$1, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L11:
	movl	32+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L12
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$2, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L12:
	movl	36+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L13
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L13:
	movl	40+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L14
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L14:
	movl	44+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L15
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$2, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L15:
	movl	48+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L16
	leal	2(%rdx), %r11d
	subl	$1, %edx
	cmovns	%edx, %r11d
	sarl	$2, %r11d
	negl	%r11d
	addl	$3, %r11d
	movl	%r11d, %r8d
	negl	%r8d
	cmovs	%r11d, %r8d
	movl	%edx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %edx
	andl	$3, %edx
	subl	%r11d, %edx
	movl	%edx, %r11d
	negl	%r11d
	cmovs	%edx, %r11d
	addl	%r11d, %r8d
	addl	%r8d, %eax
.L16:
	movl	52+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L17
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$1, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L17:
	movl	56+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L18
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	addl	$2, %r8d
	movl	%r8d, %edx
	negl	%edx
	cmovs	%r8d, %edx
	addl	%edx, %r11d
	addl	%r11d, %eax
.L18:
	movl	60+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L19
	leal	2(%rdx), %r8d
	subl	$1, %edx
	cmovns	%edx, %r8d
	sarl	$2, %r8d
	negl	%r8d
	addl	$3, %r8d
	movl	%r8d, %r11d
	negl	%r11d
	cmovs	%r8d, %r11d
	movl	%edx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %edx
	andl	$3, %edx
	subl	%edx, %r8d
	leal	3(%r11,%r8), %edx
	addl	%edx, %eax
.L19:
	testl	%eax, %eax
	je	.L20
	movl	44(%rsp), %r8d
	addl	%ecx, %eax
	cmpl	%eax, %r8d
	jl	.L21
	movl	%r9d, %edx
	call	DFS.part.0
	movl	%eax, %ecx
.L20:
	cmpl	$-1, %ecx
	jne	.L1
	movq	24(%rsp), %rax
	movq	32(%rsp), %rcx
	leaq	(%rax,%rcx,4), %rax
	movl	0(%rbp,%rax,4), %r10d
.L21:
	movq	16(%rsp), %rax
	movq	32(%rsp), %rcx
	movl	0(%rbp,%rax,4), %edx
	movl	%r10d, 0(%rbp,%rax,4)
	movq	24(%rsp), %rax
	leaq	(%rax,%rcx,4), %rax
	movl	%edx, 0(%rbp,%rax,4)
	jmp	.L3
	.cfi_endproc
.LFE44:
	.size	DFS.part.0, .-DFS.part.0
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB39:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	xorl	%r13d, %r13d
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	leaq	.LC0(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	leaq	16+Puzzle(%rip), %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
.L84:
	leaq	-16(%rbp), %rbx
.L85:
	movq	%rbx, %rsi
	movq	%r12, %rdi
	xorl	%eax, %eax
	addq	$4, %rbx
	call	__isoc99_scanf@PLT
	cmpq	%rbx, %rbp
	jne	.L85
	addq	$4, %r13
	addq	$16, %rbp
	cmpq	$16, %r13
	jne	.L84
	movl	Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L118
	movl	4+Puzzle(%rip), %ecx
	movl	8+Puzzle(%rip), %eax
	movl	12+Puzzle(%rip), %esi
	movl	%ecx, 24(%rsp)
	testl	%ecx, %ecx
	je	.L87
	movl	%eax, 24(%rsp)
	movl	12+Puzzle(%rip), %esi
	testl	%eax, %eax
	je	.L88
	movl	%esi, 24(%rsp)
	testl	%esi, %esi
	je	.L89
	movl	16+Puzzle(%rip), %ebx
	testl	%ebx, %ebx
	je	.L119
	movl	20+Puzzle(%rip), %r11d
	testl	%r11d, %r11d
	je	.L120
	movl	24+Puzzle(%rip), %r10d
	testl	%r10d, %r10d
	je	.L121
	movl	28+Puzzle(%rip), %r9d
	testl	%r9d, %r9d
	je	.L122
	movl	32+Puzzle(%rip), %r8d
	testl	%r8d, %r8d
	je	.L123
	movl	36+Puzzle(%rip), %edi
	testl	%edi, %edi
	je	.L124
	cmpl	$0, 40+Puzzle(%rip)
	je	.L125
	cmpl	$0, 44+Puzzle(%rip)
	je	.L126
	cmpl	$0, 48+Puzzle(%rip)
	je	.L193
	cmpl	$0, 52+Puzzle(%rip)
	je	.L194
	cmpl	$0, 56+Puzzle(%rip)
	je	.L195
	cmpl	$0, 60+Puzzle(%rip)
	je	.L196
.L91:
	movd	%esi, %xmm5
	movd	%ecx, %xmm6
	movd	%eax, %xmm1
	xorl	%ebp, %ebp
	movd	%edx, %xmm0
	punpckldq	%xmm5, %xmm1
	movd	28+Puzzle(%rip), %xmm7
	movd	20+Puzzle(%rip), %xmm5
	punpckldq	%xmm6, %xmm0
	movd	16+Puzzle(%rip), %xmm3
	movd	44+Puzzle(%rip), %xmm6
	punpcklqdq	%xmm1, %xmm0
	movd	24+Puzzle(%rip), %xmm1
	movd	32+Puzzle(%rip), %xmm2
	punpckldq	%xmm5, %xmm3
	movd	56+Puzzle(%rip), %xmm4
	movd	60+Puzzle(%rip), %xmm5
	punpckldq	%xmm7, %xmm1
	movd	36+Puzzle(%rip), %xmm7
	punpcklqdq	%xmm1, %xmm3
	movd	40+Puzzle(%rip), %xmm1
	punpckldq	%xmm5, %xmm4
	punpckldq	%xmm7, %xmm2
	punpckldq	%xmm6, %xmm1
	movd	52+Puzzle(%rip), %xmm6
	punpcklqdq	%xmm1, %xmm2
	movd	48+Puzzle(%rip), %xmm1
	punpckldq	%xmm6, %xmm1
	punpcklqdq	%xmm4, %xmm1
	jmp	.L94
	.p2align 4,,10
	.p2align 3
.L198:
	cmpl	%r10d, %ebp
	jl	.L114
	movl	24(%rsp), %esi
	movl	28(%rsp), %edi
	movl	%ebp, %r8d
	xorl	%ecx, %ecx
	movl	$-1, %edx
	call	DFS.part.0
	movl	%eax, %r10d
	cmpl	$-1, %eax
	jne	.L110
.L114:
	leaq	tmp(%rip), %rax
	movdqa	16+tmp(%rip), %xmm3
	movdqa	32+tmp(%rip), %xmm2
	movdqa	(%rax), %xmm0
	movdqa	48+tmp(%rip), %xmm1
	movaps	%xmm3, 16+Puzzle(%rip)
	movaps	%xmm0, Puzzle(%rip)
	movaps	%xmm2, 32+Puzzle(%rip)
	movaps	%xmm1, 48+Puzzle(%rip)
	cmpl	$99, %ebp
	je	.L197
	addl	$1, %ebp
.L94:
	pshufd	$255, %xmm1, %xmm4
	leaq	tmp(%rip), %r15
	movd	%xmm0, %r10d
	movd	%xmm2, 8(%rsp)
	movd	%xmm4, %ebx
	movdqa	%xmm1, %xmm4
	movd	%xmm3, %esi
	movaps	%xmm0, (%r15)
	punpckhdq	%xmm1, %xmm4
	movd	%xmm1, %r9d
	movaps	%xmm3, 16+tmp(%rip)
	movd	%xmm4, %r11d
	pshufd	$85, %xmm1, %xmm4
	movaps	%xmm2, 32+tmp(%rip)
	movd	%xmm4, %edx
	pshufd	$255, %xmm2, %xmm4
	movaps	%xmm1, 48+tmp(%rip)
	movd	%xmm4, 20(%rsp)
	movdqa	%xmm2, %xmm4
	punpckhdq	%xmm2, %xmm4
	movd	%xmm4, 16(%rsp)
	pshufd	$85, %xmm2, %xmm4
	movd	%xmm4, 12(%rsp)
	pshufd	$255, %xmm3, %xmm4
	movd	%xmm4, 4(%rsp)
	movdqa	%xmm3, %xmm4
	punpckhdq	%xmm3, %xmm4
	movd	%xmm4, %edi
	pshufd	$85, %xmm3, %xmm4
	movd	%xmm4, %eax
	pshufd	$255, %xmm0, %xmm4
	movd	%xmm4, %ecx
	movdqa	%xmm0, %xmm4
	punpckhdq	%xmm0, %xmm4
	movd	%xmm4, %r12d
	pshufd	$85, %xmm0, %xmm4
	movd	%xmm4, %r8d
	testl	%r10d, %r10d
	je	.L117
	leal	2(%r10), %r13d
	subl	$1, %r10d
	cmovns	%r10d, %r13d
	sarl	$2, %r13d
	movl	%r13d, %r14d
	negl	%r14d
	cmovs	%r13d, %r14d
	movl	%r10d, %r13d
	sarl	$31, %r13d
	shrl	$30, %r13d
	addl	%r13d, %r10d
	andl	$3, %r10d
	subl	%r13d, %r10d
	movl	%r10d, %r13d
	negl	%r13d
	cmovs	%r10d, %r13d
	leal	(%r14,%r13), %r10d
.L117:
	testl	%r8d, %r8d
	je	.L95
	leal	-1(%r8), %r14d
	movl	%r14d, %r15d
	sarl	$31, %r15d
	shrl	$30, %r15d
	leal	(%r14,%r15), %r13d
	andl	$3, %r13d
	subl	%r15d, %r13d
	movl	$1, %r15d
	subl	%r13d, %r15d
	movl	%r15d, %r13d
	negl	%r13d
	cmovs	%r15d, %r13d
	addl	$2, %r8d
	testl	%r14d, %r14d
	cmovns	%r14d, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r14d
	negl	%r14d
	cmovs	%r8d, %r14d
	addl	%r14d, %r13d
	addl	%r13d, %r10d
.L95:
	testl	%r12d, %r12d
	je	.L96
	leal	-1(%r12), %r13d
	movl	%r13d, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	leal	0(%r13,%r8), %r14d
	andl	$3, %r14d
	subl	%r14d, %r8d
	addl	$2, %r8d
	movl	%r8d, %r14d
	negl	%r14d
	cmovns	%r14d, %r8d
	addl	$2, %r12d
	testl	%r13d, %r13d
	cmovns	%r13d, %r12d
	sarl	$2, %r12d
	movl	%r12d, %r13d
	negl	%r13d
	cmovs	%r12d, %r13d
	addl	%r13d, %r8d
	addl	%r8d, %r10d
.L96:
	testl	%ecx, %ecx
	je	.L97
	leal	2(%rcx), %r8d
	subl	$1, %ecx
	cmovns	%ecx, %r8d
	sarl	$2, %r8d
	movl	%r8d, %r12d
	negl	%r12d
	cmovs	%r8d, %r12d
	movl	%ecx, %r8d
	sarl	$31, %r8d
	shrl	$30, %r8d
	addl	%r8d, %ecx
	andl	$3, %ecx
	subl	%ecx, %r8d
	leal	3(%r12,%r8), %ecx
	addl	%ecx, %r10d
.L97:
	testl	%esi, %esi
	je	.L98
	leal	2(%rsi), %ecx
	subl	$1, %esi
	cmovns	%esi, %ecx
	movl	%esi, %r12d
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r8d
	negl	%r8d
	cmovs	%ecx, %r8d
	sarl	$31, %r12d
	shrl	$30, %r12d
	leal	(%rsi,%r12), %ecx
	andl	$3, %ecx
	subl	%r12d, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	addl	%esi, %r8d
	addl	%r8d, %r10d
.L98:
	testl	%eax, %eax
	je	.L99
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%eax, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %eax
	andl	$3, %eax
	subl	%esi, %eax
	movl	$1, %esi
	subl	%eax, %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L99:
	testl	%edi, %edi
	je	.L100
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$1, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovs	%eax, %ecx
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %edi
	andl	$3, %edi
	subl	%edi, %eax
	leal	2(%rax), %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L100:
	movl	4(%rsp), %edi
	testl	%edi, %edi
	je	.L101
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$1, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	3(%rsi,%rax), %eax
	addl	%eax, %r10d
.L101:
	movl	8(%rsp), %eax
	testl	%eax, %eax
	je	.L102
	leal	2(%rax), %esi
	subl	$1, %eax
	cmovns	%eax, %esi
	sarl	$2, %esi
	negl	%esi
	addl	$2, %esi
	movl	%esi, %ecx
	negl	%ecx
	cmovs	%esi, %ecx
	movl	%eax, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %eax
	andl	$3, %eax
	subl	%esi, %eax
	movl	%eax, %esi
	negl	%esi
	cmovns	%esi, %eax
	addl	%eax, %ecx
	addl	%ecx, %r10d
.L102:
	movl	12(%rsp), %edi
	testl	%edi, %edi
	je	.L103
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovns	%esi, %eax
	movl	%edi, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %ecx
	andl	$3, %ecx
	subl	%esi, %ecx
	movl	$1, %esi
	subl	%ecx, %esi
	movl	%esi, %ecx
	negl	%ecx
	cmovs	%esi, %ecx
	addl	%ecx, %eax
	addl	%eax, %r10d
.L103:
	movl	16(%rsp), %edi
	testl	%edi, %edi
	je	.L104
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	2(%rax), %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%eax, %esi
	addl	%esi, %r10d
.L104:
	movl	20(%rsp), %edi
	testl	%edi, %edi
	je	.L105
	leal	2(%rdi), %eax
	subl	$1, %edi
	cmovns	%edi, %eax
	movl	%edi, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	movl	%edi, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ecx
	andl	$3, %ecx
	subl	%ecx, %eax
	leal	3(%rsi,%rax), %eax
	addl	%eax, %r10d
.L105:
	testl	%r9d, %r9d
	je	.L106
	leal	2(%r9), %eax
	subl	$1, %r9d
	cmovns	%r9d, %eax
	movl	%r9d, %ecx
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %esi
	negl	%esi
	cmovs	%eax, %esi
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r9,%rcx), %eax
	andl	$3, %eax
	subl	%ecx, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovns	%ecx, %eax
	addl	%esi, %eax
	addl	%eax, %r10d
.L106:
	testl	%edx, %edx
	je	.L107
	leal	2(%rdx), %eax
	subl	$1, %edx
	movl	$1, %esi
	cmovns	%edx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %ecx
	negl	%ecx
	cmovs	%eax, %ecx
	movl	%edx, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %edx
	andl	$3, %edx
	subl	%eax, %edx
	subl	%edx, %esi
	movl	%esi, %eax
	negl	%eax
	cmovs	%esi, %eax
	addl	%ecx, %eax
	addl	%eax, %r10d
.L107:
	testl	%r11d, %r11d
	je	.L108
	leal	2(%r11), %eax
	subl	$1, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	movl	%r11d, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %r11d
	andl	$3, %r11d
	subl	%r11d, %eax
	leal	2(%rax), %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%edx, %eax
	addl	%eax, %r10d
.L108:
	testl	%ebx, %ebx
	je	.L109
	leal	2(%rbx), %eax
	subl	$1, %ebx
	cmovns	%ebx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %edx
	negl	%edx
	cmovs	%eax, %edx
	movl	%ebx, %eax
	sarl	$31, %eax
	shrl	$30, %eax
	addl	%eax, %ebx
	andl	$3, %ebx
	subl	%ebx, %eax
	leal	3(%rdx,%rax), %eax
	addl	%eax, %r10d
.L109:
	testl	%r10d, %r10d
	jne	.L198
.L110:
	movl	%r10d, %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L115:
	addq	$40, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	xorl	%eax, %eax
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%rbp
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r13
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	ret
.L197:
	.cfi_restore_state
	movl	$-1, %edx
	leaq	.LC1(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L115
.L120:
	movl	$1, 24(%rsp)
.L87:
	movl	$1, 28(%rsp)
	jmp	.L91
.L121:
	movl	$1, 24(%rsp)
.L88:
	movl	$2, 28(%rsp)
	jmp	.L91
.L122:
	movl	$1, 24(%rsp)
.L89:
	movl	$3, 28(%rsp)
	jmp	.L91
.L118:
	movl	$0, 24(%rsp)
	movl	4+Puzzle(%rip), %ecx
	movl	8+Puzzle(%rip), %eax
	movl	12+Puzzle(%rip), %esi
.L86:
	movl	$0, 28(%rsp)
	jmp	.L91
.L196:
	movl	$3, 24(%rsp)
	jmp	.L89
.L195:
	movl	$3, 24(%rsp)
	jmp	.L88
.L194:
	movl	$3, 24(%rsp)
	jmp	.L87
.L193:
	movl	$3, 24(%rsp)
	jmp	.L86
.L126:
	movl	$2, 24(%rsp)
	jmp	.L89
.L125:
	movl	$2, 24(%rsp)
	jmp	.L88
.L124:
	movl	$2, 24(%rsp)
	jmp	.L87
.L123:
	movl	$2, 24(%rsp)
	jmp	.L86
.L119:
	movl	$1, 24(%rsp)
	jmp	.L86
	.cfi_endproc
.LFE39:
	.size	main, .-main
	.text
	.p2align 4
	.globl	Empty
	.type	Empty, @function
Empty:
.LFB40:
	.cfi_startproc
	endbr64
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L200
	movl	4+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L201
	movl	8+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L202
	movl	12+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L203
	movl	16+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L209
	movl	20+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L210
	movl	24+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L211
	movl	28+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L212
	movl	32+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L213
	movl	36+Puzzle(%rip), %r11d
	testl	%r11d, %r11d
	je	.L214
	movl	40+Puzzle(%rip), %r10d
	testl	%r10d, %r10d
	je	.L215
	movl	44+Puzzle(%rip), %r9d
	testl	%r9d, %r9d
	je	.L216
	movl	48+Puzzle(%rip), %r8d
	movl	$3, %eax
	testl	%r8d, %r8d
	je	.L200
	movl	52+Puzzle(%rip), %ecx
	movl	$3, %eax
	testl	%ecx, %ecx
	je	.L201
	movl	56+Puzzle(%rip), %edx
	movl	$3, %eax
	testl	%edx, %edx
	je	.L202
	movl	60+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L229
	ret
.L209:
	movl	$1, %eax
.L200:
	xorl	%edx, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L210:
	movl	$1, %eax
.L201:
	movl	$1, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L211:
	movl	$1, %eax
.L202:
	movl	$2, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L212:
	movl	$1, %eax
.L203:
	movl	$3, %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
.L229:
	movl	$3, %eax
	jmp	.L203
.L213:
	movl	$2, %eax
	jmp	.L200
.L214:
	movl	$2, %eax
	jmp	.L201
.L215:
	movl	$2, %eax
	jmp	.L202
.L216:
	movl	$2, %eax
	jmp	.L203
	.cfi_endproc
.LFE40:
	.size	Empty, .-Empty
	.p2align 4
	.globl	swap
	.type	swap, @function
swap:
.LFB41:
	.cfi_startproc
	endbr64
	movl	(%rdi), %eax
	movl	(%rsi), %edx
	movl	%edx, (%rdi)
	movl	%eax, (%rsi)
	ret
	.cfi_endproc
.LFE41:
	.size	swap, .-swap
	.p2align 4
	.globl	Cal
	.type	Cal, @function
Cal:
.LFB42:
	.cfi_startproc
	endbr64
	movl	Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L232
	leal	2(%rax), %edx
	subl	$1, %eax
	cmovns	%eax, %edx
	sarl	$2, %edx
	movl	%edx, %ecx
	negl	%ecx
	cmovs	%edx, %ecx
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	addl	%ecx, %eax
.L232:
	movl	4+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L233
	leal	-1(%rdx), %esi
	movl	%esi, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rsi,%rcx), %edi
	andl	$3, %edi
	subl	%edi, %ecx
	leal	1(%rcx), %edi
	movl	%edi, %ecx
	negl	%ecx
	cmovs	%edi, %ecx
	addl	$2, %edx
	testl	%esi, %esi
	cmovns	%esi, %edx
	sarl	$2, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L233:
	movl	8+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L234
	leal	-1(%rdx), %esi
	movl	%esi, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rsi,%rcx), %edi
	andl	$3, %edi
	subl	%edi, %ecx
	leal	2(%rcx), %edi
	movl	%edi, %ecx
	negl	%ecx
	cmovs	%edi, %ecx
	addl	$2, %edx
	testl	%esi, %esi
	cmovns	%esi, %edx
	sarl	$2, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L234:
	movl	12+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L235
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L235:
	movl	16+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L236
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L236:
	movl	20+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L237
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L237:
	movl	24+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L238
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L238:
	movl	28+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L239
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L239:
	movl	32+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L240
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L240:
	movl	36+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L241
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L241:
	movl	40+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L242
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L242:
	movl	44+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L243
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L243:
	movl	48+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L244
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovns	%esi, %ecx
	movl	%edx, %esi
	sarl	$31, %esi
	shrl	$30, %esi
	addl	%esi, %edx
	andl	$3, %edx
	subl	%esi, %edx
	movl	%edx, %esi
	negl	%esi
	cmovns	%esi, %edx
	addl	%ecx, %edx
	addl	%edx, %eax
.L244:
	movl	52+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L245
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$1, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L245:
	movl	56+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L246
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	addl	$2, %ecx
	movl	%ecx, %edx
	negl	%edx
	cmovs	%ecx, %edx
	addl	%esi, %edx
	addl	%edx, %eax
.L246:
	movl	60+Puzzle(%rip), %edx
	testl	%edx, %edx
	je	.L231
	leal	2(%rdx), %ecx
	subl	$1, %edx
	cmovns	%edx, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %esi
	negl	%esi
	cmovs	%ecx, %esi
	movl	%edx, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %edx
	andl	$3, %edx
	subl	%edx, %ecx
	leal	3(%rsi,%rcx), %edx
	addl	%edx, %eax
.L231:
	ret
	.cfi_endproc
.LFE42:
	.size	Cal, .-Cal
	.p2align 4
	.globl	DFS
	.type	DFS, @function
DFS:
.LFB43:
	.cfi_startproc
	endbr64
	movl	%edx, %r9d
	movl	Puzzle(%rip), %edx
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movl	%ecx, %r10d
	testl	%edx, %edx
	je	.L297
	leal	2(%rdx), %eax
	subl	$1, %edx
	cmovns	%edx, %eax
	movl	%edx, %ecx
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovs	%eax, %r11d
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%rdx,%rcx), %eax
	andl	$3, %eax
	subl	%ecx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	leal	(%r11,%rax), %edx
.L297:
	movl	4+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L298
	leal	-1(%rax), %r11d
	movl	%r11d, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r11,%rcx), %ebx
	andl	$3, %ebx
	subl	%ebx, %ecx
	leal	1(%rcx), %ebx
	movl	%ebx, %ecx
	negl	%ecx
	cmovs	%ebx, %ecx
	addl	$2, %eax
	testl	%r11d, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L298:
	movl	8+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L299
	leal	-1(%rax), %r11d
	movl	%r11d, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	leal	(%r11,%rcx), %ebx
	andl	$3, %ebx
	subl	%ebx, %ecx
	leal	2(%rcx), %ebx
	movl	%ebx, %ecx
	negl	%ecx
	cmovs	%ebx, %ecx
	addl	$2, %eax
	testl	%r11d, %r11d
	cmovns	%r11d, %eax
	sarl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L299:
	movl	12+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L300
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L300:
	movl	16+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L301
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	movl	%eax, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %eax
	andl	$3, %eax
	subl	%r11d, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	addl	%ecx, %eax
	addl	%eax, %edx
.L301:
	movl	20+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L302
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L302:
	movl	24+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L303
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L303:
	movl	28+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L304
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$1, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L304:
	movl	32+Puzzle(%rip), %ecx
	testl	%ecx, %ecx
	je	.L305
	leal	2(%rcx), %eax
	subl	$1, %ecx
	cmovns	%ecx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$2, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	movl	%ecx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %ecx
	andl	$3, %ecx
	subl	%r11d, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	addl	%ecx, %eax
	addl	%eax, %edx
.L305:
	movl	36+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L306
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L306:
	movl	40+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L307
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L307:
	movl	44+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L308
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$2, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
.L308:
	movl	48+Puzzle(%rip), %ecx
	testl	%ecx, %ecx
	je	.L309
	leal	2(%rcx), %eax
	subl	$1, %ecx
	cmovns	%ecx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	$3, %eax
	movl	%eax, %r11d
	negl	%r11d
	cmovns	%r11d, %eax
	movl	%ecx, %r11d
	sarl	$31, %r11d
	shrl	$30, %r11d
	addl	%r11d, %ecx
	andl	$3, %ecx
	subl	%r11d, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovns	%r11d, %ecx
	addl	%ecx, %eax
	addl	%eax, %edx
.L309:
	movl	52+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L310
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$1, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L310:
	movl	56+Puzzle(%rip), %eax
	testl	%eax, %eax
	je	.L311
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	addl	$2, %ecx
	movl	%ecx, %eax
	negl	%eax
	cmovs	%ecx, %eax
	addl	%r11d, %eax
	addl	%eax, %edx
.L311:
	movl	60+Puzzle(%rip), %eax
	testl	%eax, %eax
	jne	.L365
	testl	%edx, %edx
	je	.L314
.L366:
	addl	%r10d, %edx
	cmpl	%r8d, %edx
	jg	.L315
	movl	%r10d, %ecx
	movl	%r9d, %edx
	popq	%rbx
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	jmp	DFS.part.0
	.p2align 4,,10
	.p2align 3
.L365:
	.cfi_restore_state
	leal	2(%rax), %ecx
	subl	$1, %eax
	cmovns	%eax, %ecx
	sarl	$2, %ecx
	negl	%ecx
	addl	$3, %ecx
	movl	%ecx, %r11d
	negl	%r11d
	cmovs	%ecx, %r11d
	movl	%eax, %ecx
	sarl	$31, %ecx
	shrl	$30, %ecx
	addl	%ecx, %eax
	andl	$3, %eax
	subl	%eax, %ecx
	leal	3(%r11,%rcx), %eax
	addl	%eax, %edx
	testl	%edx, %edx
	jne	.L366
.L314:
	movl	%r10d, %eax
	popq	%rbx
	.cfi_remember_state
	.cfi_def_cfa_offset 8
	ret
.L315:
	.cfi_restore_state
	movl	$-1, %eax
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE43:
	.size	DFS, .-DFS
	.globl	dy
	.data
	.align 16
	.type	dy, @object
	.size	dy, 16
dy:
	.long	1
	.long	0
	.long	-1
	.long	0
	.globl	dx
	.align 16
	.type	dx, @object
	.size	dx, 16
dx:
	.long	0
	.long	1
	.long	0
	.long	-1
	.globl	tmp
	.bss
	.align 32
	.type	tmp, @object
	.size	tmp, 64
tmp:
	.zero	64
	.globl	Puzzle
	.align 32
	.type	Puzzle, @object
	.size	Puzzle, 64
Puzzle:
	.zero	64
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:

#include<stdio.h>
#include<stdlib.h>

int Puzzle[4][4];
int tmp[4][4];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void Empty(int *, int *);
void swap(int *, int *);
int Cal();
int DFS(int, int, int, int, int);

int main(){
  int i, j, l;
  int x, y, a;

for(i=0;i<4;i++)
  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      scanf("%d",&Puzzle[i][j]);
    }
  }

  Empty(&x,&y);

  for(l = 0 ; l < 100 ; l++){
    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 tmp[i][j] = Puzzle[i][j];
      }
    }

    a = DFS(x, y, -1, 0, l);
    if(a != -1){
      printf("%d\n",a);
      break;
    }

    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 Puzzle[i][j] = tmp[i][j];
      }
    }

    a = -1;
    if(l == 99) printf("%d\n",a);
  }

  return 0;
}

void Empty(int *x, int *y){
  int i, j;

  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      if(!Puzzle[i][j]){
 *x = j;
 *y = i;
 return;
      }
    }
  }
}

void swap(int *a, int *b){
  int tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}


int Cal(){
  int i, a;
  int sum = 0;

  for(i = 0 ; i < 16 ; i++){
    a = Puzzle[i/4][i%4];
    if(a){
      a--;
      sum += abs(i/4 - a/4)  + abs(i%4 - a%4);
    }
  }

  return sum;
}

int DFS(int x, int y, int p, int dep, int limit){
  int i, h, nx, ny, res;

  h = Cal();

  if(h == 0) return dep;
  if(dep + h > limit) return -1;

  for(i = 0 ; i < 4 ; i++){
    nx = x + dx[i];
    ny = y + dy[i];

    if(~p && i == (p+2)%4) continue;
    if(!(0 <= nx && nx < 4 && 0 <= ny && ny < 4)) continue;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
    res = DFS(nx, ny, i, dep+1, limit);
    if(~res) return res;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
  }

  return -1;
}



0 2 3 4
6 7 8 0
5 10 11 12
9 13 14 15
 0 4 3 0
6 7 8 0
5 10 11 12
9 13 14 15
 0 4 3 0
6 7 8 0
5 10 11 12
9 13 14 0
 0 2 3 8
6 7 0 0
5 10 11 12
9 13 14 15
 0 2 3 0
6 7 4 0
5 10 11 12
9 13 14 15
 0 0 3 1
6 7 8 0
5 10 4 12
9 13 14 15
 0 2 3 8
6 7 0 0
0 10 11 12
9 13 14 15
 0 2 3 8
6 7 0 0
0 10 5 12
9 13 14 15
 0 2 3 4
6 7 0 0
0 10 11 12
9 13 14 15
 0 0 2 0
6 7 8 0
5 10 11 12
9 13 14 15

28
 30
 29
 26
 26
 32
 26
 27
 18
 12

Given the following C code and unoptimized assembly code, your task is to generate highly optimized x86-64 assembly code.
C Code:

```c
#include<stdio.h>
#include<stdlib.h>

int Puzzle[4][4];
int tmp[4][4];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};

void Empty(int *, int *);
void swap(int *, int *);
int Cal();
int DFS(int, int, int, int, int);

int main(){
  int i, j, l;
  int x, y, a;

for(i=0;i<4;i++)
  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      scanf("%d",&Puzzle[i][j]);
    }
  }

  Empty(&x,&y);

  for(l = 0 ; l < 100 ; l++){
    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 tmp[i][j] = Puzzle[i][j];
      }
    }

    a = DFS(x, y, -1, 0, l);
    if(a != -1){
      printf("%d\n",a);
      break;
    }

    for(i = 0 ; i < 4 ; i++){
      for(j = 0 ; j < 4 ; j++){
 Puzzle[i][j] = tmp[i][j];
      }
    }

    a = -1;
    if(l == 99) printf("%d\n",a);
  }

  return 0;
}

void Empty(int *x, int *y){
  int i, j;

  for(i = 0 ; i < 4 ; i++){
    for(j = 0 ; j < 4 ; j++){
      if(!Puzzle[i][j]){
 *x = j;
 *y = i;
 return;
      }
    }
  }
}

void swap(int *a, int *b){
  int tmp;

  tmp = *a;
  *a = *b;
  *b = tmp;
}


int Cal(){
  int i, a;
  int sum = 0;

  for(i = 0 ; i < 16 ; i++){
    a = Puzzle[i/4][i%4];
    if(a){
      a--;
      sum += abs(i/4 - a/4)  + abs(i%4 - a%4);
    }
  }

  return sum;
}

int DFS(int x, int y, int p, int dep, int limit){
  int i, h, nx, ny, res;

  h = Cal();

  if(h == 0) return dep;
  if(dep + h > limit) return -1;

  for(i = 0 ; i < 4 ; i++){
    nx = x + dx[i];
    ny = y + dy[i];

    if(~p && i == (p+2)%4) continue;
    if(!(0 <= nx && nx < 4 && 0 <= ny && ny < 4)) continue;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
    res = DFS(nx, ny, i, dep+1, limit);
    if(~res) return res;

    swap(&Puzzle[y][x], &Puzzle[ny][nx]);
  }

  return -1;
}


```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	Puzzle
	.bss
	.align 32
	.type	Puzzle, @object
	.size	Puzzle, 64
Puzzle:
	.zero	64
	.globl	tmp
	.align 32
	.type	tmp, @object
	.size	tmp, 64
tmp:
	.zero	64
	.globl	dx
	.data
	.align 16
	.type	dx, @object
	.size	dx, 16
dx:
	.long	0
	.long	1
	.long	0
	.long	-1
	.globl	dy
	.align 16
	.type	dy, @object
	.size	dy, 16
dy:
	.long	1
	.long	0
	.long	-1
	.long	0
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	movl	$0, -24(%rbp)
	jmp	.L2
.L7:
	movl	$0, -24(%rbp)
	jmp	.L3
.L6:
	movl	$0, -20(%rbp)
	jmp	.L4
.L5:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -20(%rbp)
.L4:
	cmpl	$3, -20(%rbp)
	jle	.L5
	addl	$1, -24(%rbp)
.L3:
	cmpl	$3, -24(%rbp)
	jle	.L6
	addl	$1, -24(%rbp)
.L2:
	cmpl	$3, -24(%rbp)
	jle	.L7
	leaq	-28(%rbp), %rdx
	leaq	-32(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	Empty
	movl	$0, -16(%rbp)
	jmp	.L8
.L20:
	movl	$0, -24(%rbp)
	jmp	.L9
.L12:
	movl	$0, -20(%rbp)
	jmp	.L10
.L11:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	tmp(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L10:
	cmpl	$3, -20(%rbp)
	jle	.L11
	addl	$1, -24(%rbp)
.L9:
	cmpl	$3, -24(%rbp)
	jle	.L12
	movl	-28(%rbp), %esi
	movl	-32(%rbp), %eax
	movl	-16(%rbp), %edx
	movl	%edx, %r8d
	movl	$0, %ecx
	movl	$-1, %edx
	movl	%eax, %edi
	call	DFS
	movl	%eax, -12(%rbp)
	cmpl	$-1, -12(%rbp)
	je	.L13
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L14
.L13:
	movl	$0, -24(%rbp)
	jmp	.L15
.L18:
	movl	$0, -20(%rbp)
	jmp	.L16
.L17:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	tmp(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	Puzzle(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L16:
	cmpl	$3, -20(%rbp)
	jle	.L17
	addl	$1, -24(%rbp)
.L15:
	cmpl	$3, -24(%rbp)
	jle	.L18
	movl	$-1, -12(%rbp)
	cmpl	$99, -16(%rbp)
	jne	.L19
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L19:
	addl	$1, -16(%rbp)
.L8:
	cmpl	$99, -16(%rbp)
	jle	.L20
.L14:
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L22
	call	__stack_chk_fail@PLT
.L22:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	main, .-main
	.globl	Empty
	.type	Empty, @function
Empty:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L24
.L29:
	movl	$0, -4(%rbp)
	jmp	.L25
.L28:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L26
	movq	-24(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-8(%rbp), %edx
	movl	%edx, (%rax)
	jmp	.L23
.L26:
	addl	$1, -4(%rbp)
.L25:
	cmpl	$3, -4(%rbp)
	jle	.L28
	addl	$1, -8(%rbp)
.L24:
	cmpl	$3, -8(%rbp)
	jle	.L29
.L23:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	Empty, .-Empty
	.globl	swap
	.type	swap, @function
swap:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movq	-24(%rbp), %rax
	movl	(%rax), %eax
	movl	%eax, -4(%rbp)
	movq	-32(%rbp), %rax
	movl	(%rax), %edx
	movq	-24(%rbp), %rax
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	swap, .-swap
	.globl	Cal
	.type	Cal, @function
Cal:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	$0, -8(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L32
.L34:
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movslq	%eax, %rdx
	movslq	%ecx, %rax
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	cmpl	$0, -4(%rbp)
	je	.L33
	subl	$1, -4(%rbp)
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-4(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	%ecx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %esi
	movl	-4(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	movl	%esi, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	addl	%ecx, %eax
	addl	%eax, -8(%rbp)
.L33:
	addl	$1, -12(%rbp)
.L32:
	cmpl	$15, -12(%rbp)
	jle	.L34
	movl	-8(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	Cal, .-Cal
	.globl	DFS
	.type	DFS, @function
DFS:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movl	%edi, -36(%rbp)
	movl	%esi, -40(%rbp)
	movl	%edx, -44(%rbp)
	movl	%ecx, -48(%rbp)
	movl	%r8d, -52(%rbp)
	movl	$0, %eax
	call	Cal
	movl	%eax, -16(%rbp)
	cmpl	$0, -16(%rbp)
	jne	.L37
	movl	-48(%rbp), %eax
	jmp	.L38
.L37:
	movl	-48(%rbp), %edx
	movl	-16(%rbp), %eax
	addl	%edx, %eax
	cmpl	%eax, -52(%rbp)
	jge	.L39
	movl	$-1, %eax
	jmp	.L38
.L39:
	movl	$0, -20(%rbp)
	jmp	.L40
.L46:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dx(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-36(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -12(%rbp)
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dy(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-40(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -8(%rbp)
	cmpl	$-1, -44(%rbp)
	je	.L41
	movl	-44(%rbp), %eax
	addl	$2, %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	cmpl	%eax, -20(%rbp)
	je	.L47
.L41:
	cmpl	$0, -12(%rbp)
	js	.L48
	cmpl	$3, -12(%rbp)
	jg	.L48
	cmpl	$0, -8(%rbp)
	js	.L48
	cmpl	$3, -8(%rbp)
	jg	.L48
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	movl	-48(%rbp), %eax
	leal	1(%rax), %ecx
	movl	-52(%rbp), %edi
	movl	-20(%rbp), %edx
	movl	-8(%rbp), %esi
	movl	-12(%rbp), %eax
	movl	%edi, %r8d
	movl	%eax, %edi
	call	DFS
	movl	%eax, -4(%rbp)
	cmpl	$-1, -4(%rbp)
	je	.L45
	movl	-4(%rbp), %eax
	jmp	.L38
.L45:
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	jmp	.L42
.L47:
	nop
	jmp	.L42
.L48:
	nop
.L42:
	addl	$1, -20(%rbp)
.L40:
	cmpl	$3, -20(%rbp)
	jle	.L46
	movl	$-1, %eax
.L38:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	DFS, .-DFS
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
```

Only output the optimized assembly code. Do not include any other text. Do not write any comments in the assembly code. Wrap the assembly code in ```assembly``` tags.
train
	.file	"temp.c"
	.text
	.globl	Puzzle
	.bss
	.align 32
	.type	Puzzle, @object
	.size	Puzzle, 64
Puzzle:
	.zero	64
	.globl	tmp
	.align 32
	.type	tmp, @object
	.size	tmp, 64
tmp:
	.zero	64
	.globl	dx
	.data
	.align 16
	.type	dx, @object
	.size	dx, 16
dx:
	.long	0
	.long	1
	.long	0
	.long	-1
	.globl	dy
	.align 16
	.type	dy, @object
	.size	dy, 16
dy:
	.long	1
	.long	0
	.long	-1
	.long	0
	.section	.rodata
.LC0:
	.string	"%d"
.LC1:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB6:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$32, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	movl	$0, -24(%rbp)
	jmp	.L2
.L7:
	movl	$0, -24(%rbp)
	jmp	.L3
.L6:
	movl	$0, -20(%rbp)
	jmp	.L4
.L5:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rdx, %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	addl	$1, -20(%rbp)
.L4:
	cmpl	$3, -20(%rbp)
	jle	.L5
	addl	$1, -24(%rbp)
.L3:
	cmpl	$3, -24(%rbp)
	jle	.L6
	addl	$1, -24(%rbp)
.L2:
	cmpl	$3, -24(%rbp)
	jle	.L7
	leaq	-28(%rbp), %rdx
	leaq	-32(%rbp), %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	Empty
	movl	$0, -16(%rbp)
	jmp	.L8
.L20:
	movl	$0, -24(%rbp)
	jmp	.L9
.L12:
	movl	$0, -20(%rbp)
	jmp	.L10
.L11:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	tmp(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L10:
	cmpl	$3, -20(%rbp)
	jle	.L11
	addl	$1, -24(%rbp)
.L9:
	cmpl	$3, -24(%rbp)
	jle	.L12
	movl	-28(%rbp), %esi
	movl	-32(%rbp), %eax
	movl	-16(%rbp), %edx
	movl	%edx, %r8d
	movl	$0, %ecx
	movl	$-1, %edx
	movl	%eax, %edi
	call	DFS
	movl	%eax, -12(%rbp)
	cmpl	$-1, -12(%rbp)
	je	.L13
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L14
.L13:
	movl	$0, -24(%rbp)
	jmp	.L15
.L18:
	movl	$0, -20(%rbp)
	jmp	.L16
.L17:
	movl	-20(%rbp), %eax
	movslq	%eax, %rdx
	movl	-24(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	tmp(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	-20(%rbp), %edx
	movslq	%edx, %rcx
	movl	-24(%rbp), %edx
	movslq	%edx, %rdx
	salq	$2, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	Puzzle(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	addl	$1, -20(%rbp)
.L16:
	cmpl	$3, -20(%rbp)
	jle	.L17
	addl	$1, -24(%rbp)
.L15:
	cmpl	$3, -24(%rbp)
	jle	.L18
	movl	$-1, -12(%rbp)
	cmpl	$99, -16(%rbp)
	jne	.L19
	movl	-12(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
.L19:
	addl	$1, -16(%rbp)
.L8:
	cmpl	$99, -16(%rbp)
	jle	.L20
.L14:
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L22
	call	__stack_chk_fail@PLT
.L22:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	main, .-main
	.globl	Empty
	.type	Empty, @function
Empty:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L24
.L29:
	movl	$0, -4(%rbp)
	jmp	.L25
.L28:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L26
	movq	-24(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-8(%rbp), %edx
	movl	%edx, (%rax)
	jmp	.L23
.L26:
	addl	$1, -4(%rbp)
.L25:
	cmpl	$3, -4(%rbp)
	jle	.L28
	addl	$1, -8(%rbp)
.L24:
	cmpl	$3, -8(%rbp)
	jle	.L29
.L23:
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	Empty, .-Empty
	.globl	swap
	.type	swap, @function
swap:
.LFB8:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, -24(%rbp)
	movq	%rsi, -32(%rbp)
	movq	-24(%rbp), %rax
	movl	(%rax), %eax
	movl	%eax, -4(%rbp)
	movq	-32(%rbp), %rax
	movl	(%rax), %edx
	movq	-24(%rbp), %rax
	movl	%edx, (%rax)
	movq	-32(%rbp), %rax
	movl	-4(%rbp), %edx
	movl	%edx, (%rax)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE8:
	.size	swap, .-swap
	.globl	Cal
	.type	Cal, @function
Cal:
.LFB9:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	$0, -8(%rbp)
	movl	$0, -12(%rbp)
	jmp	.L32
.L34:
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movslq	%eax, %rdx
	movslq	%ecx, %rax
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	cmpl	$0, -4(%rbp)
	je	.L33
	subl	$1, -4(%rbp)
	movl	-12(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	movl	%eax, %ecx
	movl	-4(%rbp), %eax
	leal	3(%rax), %edx
	testl	%eax, %eax
	cmovs	%edx, %eax
	sarl	$2, %eax
	negl	%eax
	addl	%ecx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	movl	%eax, %ecx
	movl	-12(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %esi
	movl	-4(%rbp), %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	movl	%esi, %eax
	subl	%edx, %eax
	movl	%eax, %edx
	negl	%edx
	cmovns	%edx, %eax
	addl	%ecx, %eax
	addl	%eax, -8(%rbp)
.L33:
	addl	$1, -12(%rbp)
.L32:
	cmpl	$15, -12(%rbp)
	jle	.L34
	movl	-8(%rbp), %eax
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE9:
	.size	Cal, .-Cal
	.globl	DFS
	.type	DFS, @function
DFS:
.LFB10:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$64, %rsp
	movl	%edi, -36(%rbp)
	movl	%esi, -40(%rbp)
	movl	%edx, -44(%rbp)
	movl	%ecx, -48(%rbp)
	movl	%r8d, -52(%rbp)
	movl	$0, %eax
	call	Cal
	movl	%eax, -16(%rbp)
	cmpl	$0, -16(%rbp)
	jne	.L37
	movl	-48(%rbp), %eax
	jmp	.L38
.L37:
	movl	-48(%rbp), %edx
	movl	-16(%rbp), %eax
	addl	%edx, %eax
	cmpl	%eax, -52(%rbp)
	jge	.L39
	movl	$-1, %eax
	jmp	.L38
.L39:
	movl	$0, -20(%rbp)
	jmp	.L40
.L46:
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dx(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-36(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -12(%rbp)
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	dy(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	-40(%rbp), %eax
	addl	%edx, %eax
	movl	%eax, -8(%rbp)
	cmpl	$-1, -44(%rbp)
	je	.L41
	movl	-44(%rbp), %eax
	addl	$2, %eax
	cltd
	shrl	$30, %edx
	addl	%edx, %eax
	andl	$3, %eax
	subl	%edx, %eax
	cmpl	%eax, -20(%rbp)
	je	.L47
.L41:
	cmpl	$0, -12(%rbp)
	js	.L48
	cmpl	$3, -12(%rbp)
	jg	.L48
	cmpl	$0, -8(%rbp)
	js	.L48
	cmpl	$3, -8(%rbp)
	jg	.L48
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	movl	-48(%rbp), %eax
	leal	1(%rax), %ecx
	movl	-52(%rbp), %edi
	movl	-20(%rbp), %edx
	movl	-8(%rbp), %esi
	movl	-12(%rbp), %eax
	movl	%edi, %r8d
	movl	%eax, %edi
	call	DFS
	movl	%eax, -4(%rbp)
	cmpl	$-1, -4(%rbp)
	je	.L45
	movl	-4(%rbp), %eax
	jmp	.L38
.L45:
	movl	-12(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	Puzzle(%rip), %rax
	addq	%rax, %rdx
	movl	-36(%rbp), %eax
	movslq	%eax, %rcx
	movl	-40(%rbp), %eax
	cltq
	salq	$2, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rcx
	leaq	Puzzle(%rip), %rax
	addq	%rcx, %rax
	movq	%rdx, %rsi
	movq	%rax, %rdi
	call	swap
	jmp	.L42
.L47:
	nop
	jmp	.L42
.L48:
	nop
.L42:
	addl	$1, -20(%rbp)
.L40:
	cmpl	$3, -20(%rbp)
	jle	.L46
	movl	$-1, %eax
.L38:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE10:
	.size	DFS, .-DFS
	.ident	"GCC: (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0"
	.section	.note.GNU-stack,"",@progbits
	.section	.note.gnu.property,"a"
	.align 8
	.long	1f - 0f
	.long	4f - 1f
	.long	5
0:
	.string	"GNU"
1:
	.align 8
	.long	0xc0000002
	.long	3f - 2f
2:
	.long	0x3
3:
	.align 8
4:
