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>

typedef struct{
  int x,y,t;
}Point;

Point Q[10000];
int head,tail;
char map[1000][1000];
Point p,next;
int h,w,n;
int visited[1000][1000];
  

void enqueue(Point n){
  Q[tail] = n;
  tail = (tail+1)%10000;
}

Point  dequeue(){
  Point re;
  re = Q[head];
  head = (head+1)%10000;
  return re;
}


int bfs(Point start,char end){
  int i,j;
  for(i=0;i<h;i++)
    for(j=0;j<w;j++)
      visited[i][j]=0;

  head = 0;
  tail = 0;
  enqueue(start);
  while(head != tail){
    p = dequeue();

    if(map[p.x][p.y] == end) break;
    else  p.t++;

    if(p.x+1 < h &&  map[p.x+1][p.y] != 'X' && visited[p.x+1][p.y]==0){
      next=p;
      next.x++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.x-1 >= 0 && map[p.x-1][p.y] != 'X' && visited[p.x-1][p.y]==0){
      next=p;
      next.x--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y+1 < w && map[p.x][p.y+1] != 'X' && visited[p.x][p.y+1]==0){
      next=p;
      next.y++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y-1 >= 0 && map[p.x][p.y-1] != 'X' && visited[p.x][p.y-1]==0){
      next=p;
      next.y--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
  }
  return p.t;
}
  

int main (){
  int i,j,k;
  int time;
  char hp,str[2000];
  Point start;

  scanf("%d %d %d",&h,&w,&n);
  for(i=0;i<h;i++){
    scanf("%s",str);
    for(j=0;j<w;j++){
      map[i][j] = str[j];
      if(map[i][j] == 'S'){
	start.x = i;
	start.y = j;
      }
    }
  }
  /*
  printf("\n");
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      printf("%c",map[i][j]);
    }
    printf("\n");
  }
  */
  hp=1;
  time = 0;

  while(hp<=n){
    start.t=0;
    time += bfs(start,'0'+hp);
    hp++;
    start = p;
  }
  printf("%d\n",time);

  return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	Q
	.bss
	.align 32
	.type	Q, @object
	.size	Q, 120000
Q:
	.zero	120000
	.globl	head
	.align 4
	.type	head, @object
	.size	head, 4
head:
	.zero	4
	.globl	tail
	.align 4
	.type	tail, @object
	.size	tail, 4
tail:
	.zero	4
	.globl	map
	.align 32
	.type	map, @object
	.size	map, 1000000
map:
	.zero	1000000
	.globl	p
	.align 8
	.type	p, @object
	.size	p, 12
p:
	.zero	12
	.globl	next
	.align 8
	.type	next, @object
	.size	next, 12
next:
	.zero	12
	.globl	h
	.align 4
	.type	h, @object
	.size	h, 4
h:
	.zero	4
	.globl	w
	.align 4
	.type	w, @object
	.size	w, 4
w:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	visited
	.align 32
	.type	visited, @object
	.size	visited, 4000000
visited:
	.zero	4000000
	.text
	.globl	enqueue
	.type	enqueue, @function
enqueue:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, %rdx
	movl	%esi, %eax
	movq	%rdx, -16(%rbp)
	movl	%eax, -8(%rbp)
	movl	tail(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	-16(%rbp), %rcx
	movq	%rcx, (%rdx,%rax)
	movl	-8(%rbp), %ecx
	movl	%ecx, 8(%rdx,%rax)
	movl	tail(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, tail(%rip)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	enqueue, .-enqueue
	.globl	dequeue
	.type	dequeue, @function
dequeue:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	head(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	(%rdx,%rax), %rcx
	movq	%rcx, -24(%rbp)
	movl	8(%rdx,%rax), %eax
	movl	%eax, -16(%rbp)
	movl	head(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, head(%rip)
	movq	-24(%rbp), %rax
	movq	%rax, -12(%rbp)
	movl	-16(%rbp), %eax
	movl	%eax, -4(%rbp)
	movq	-12(%rbp), %rax
	movl	-4(%rbp), %ecx
	movq	%rcx, %rdx
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	dequeue, .-dequeue
	.globl	bfs
	.type	bfs, @function
bfs:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$48, %rsp
	movq	%rdi, %rcx
	movl	%esi, %eax
	movq	%rcx, -32(%rbp)
	movl	%eax, -24(%rbp)
	movl	%edx, %eax
	movb	%al, -36(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L5
.L8:
	movl	$0, -4(%rbp)
	jmp	.L6
.L7:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$0, (%rdx,%rax)
	addl	$1, -4(%rbp)
.L6:
	movl	w(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L7
	addl	$1, -8(%rbp)
.L5:
	movl	h(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L8
	movl	$0, head(%rip)
	movl	$0, tail(%rip)
	movq	-32(%rbp), %rdx
	movl	-24(%rbp), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	jmp	.L9
.L15:
	movl	$0, %eax
	call	dequeue
	movq	%rax, p(%rip)
	movl	8+p(%rip), %eax
	andl	$0, %eax
	orl	%edx, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	%al, -36(%rbp)
	je	.L17
	movl	8+p(%rip), %eax
	addl	$1, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	h(%rip), %eax
	cmpl	%eax, %edx
	jge	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L12
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	addl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L12:
	movl	p(%rip), %eax
	testl	%eax, %eax
	jle	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L13
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	subl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L13:
	movl	4+p(%rip), %eax
	leal	1(%rax), %edx
	movl	w(%rip), %eax
	cmpl	%eax, %edx
	jge	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L14
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	addl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L14:
	movl	4+p(%rip), %eax
	testl	%eax, %eax
	jle	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L9
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	subl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L9:
	movl	head(%rip), %edx
	movl	tail(%rip), %eax
	cmpl	%eax, %edx
	jne	.L15
	jmp	.L11
.L17:
	nop
.L11:
	movl	8+p(%rip), %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	bfs, .-bfs
	.section	.rodata
.LC0:
	.string	"%d %d %d"
.LC1:
	.string	"%s"
.LC2:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB3:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$2048, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	leaq	n(%rip), %rax
	movq	%rax, %rcx
	leaq	w(%rip), %rax
	movq	%rax, %rdx
	leaq	h(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2040(%rbp)
	jmp	.L19
.L23:
	leaq	-2016(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2036(%rbp)
	jmp	.L20
.L22:
	movl	-2036(%rbp), %eax
	cltq
	movzbl	-2016(%rbp,%rax), %eax
	movl	-2036(%rbp), %edx
	movslq	%edx, %rcx
	movl	-2040(%rbp), %edx
	movslq	%edx, %rdx
	imulq	$1000, %rdx, %rdx
	addq	%rdx, %rcx
	leaq	map(%rip), %rdx
	addq	%rcx, %rdx
	movb	%al, (%rdx)
	movl	-2036(%rbp), %eax
	movslq	%eax, %rdx
	movl	-2040(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$83, %al
	jne	.L21
	movl	-2040(%rbp), %eax
	movl	%eax, -2028(%rbp)
	movl	-2036(%rbp), %eax
	movl	%eax, -2024(%rbp)
.L21:
	addl	$1, -2036(%rbp)
.L20:
	movl	w(%rip), %eax
	cmpl	%eax, -2036(%rbp)
	jl	.L22
	addl	$1, -2040(%rbp)
.L19:
	movl	h(%rip), %eax
	cmpl	%eax, -2040(%rbp)
	jl	.L23
	movb	$1, -2041(%rbp)
	movl	$0, -2032(%rbp)
	jmp	.L24
.L25:
	movl	$0, -2020(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$48, %eax
	movsbl	%al, %edx
	movq	-2028(%rbp), %rcx
	movl	-2020(%rbp), %eax
	movq	%rcx, %rdi
	movl	%eax, %esi
	call	bfs
	addl	%eax, -2032(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$1, %eax
	movb	%al, -2041(%rbp)
	movq	p(%rip), %rax
	movq	%rax, -2028(%rbp)
	movl	8+p(%rip), %eax
	movl	%eax, -2020(%rbp)
.L24:
	movsbl	-2041(%rbp), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jle	.L25
	movl	-2032(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L27
	call	__stack_chk_fail@PLT
.L27:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE3:
	.size	main, .-main
	.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
	.globl	enqueue
	.type	enqueue, @function
enqueue:
.LFB23:
	.cfi_startproc
	endbr64
	movslq	tail(%rip), %rax
	leaq	(%rax,%rax,2), %rcx
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	leaq	(%rax,%rcx,4), %rax
	addl	$1, %edx
	movq	%rdi, (%rax)
	movl	%edx, %ecx
	movl	%esi, 8(%rax)
	movslq	%edx, %rax
	sarl	$31, %ecx
	imulq	$1759218605, %rax, %rax
	sarq	$44, %rax
	subl	%ecx, %eax
	imull	$10000, %eax, %eax
	subl	%eax, %edx
	movl	%edx, tail(%rip)
	ret
	.cfi_endproc
.LFE23:
	.size	enqueue, .-enqueue
	.p2align 4
	.globl	dequeue
	.type	dequeue, @function
dequeue:
.LFB24:
	.cfi_startproc
	endbr64
	movslq	head(%rip), %rax
	leaq	Q(%rip), %rsi
	movq	%rax, %rdx
	leaq	(%rax,%rax,2), %rcx
	addl	$1, %edx
	salq	$2, %rcx
	movslq	%edx, %rax
	movl	%edx, %edi
	imulq	$1759218605, %rax, %rax
	sarl	$31, %edi
	sarq	$44, %rax
	subl	%edi, %eax
	imull	$10000, %eax, %eax
	subl	%eax, %edx
	movl	%edx, head(%rip)
	movl	8(%rsi,%rcx), %edx
	movq	(%rsi,%rcx), %rax
	ret
	.cfi_endproc
.LFE24:
	.size	dequeue, .-dequeue
	.p2align 4
	.globl	bfs
	.type	bfs, @function
bfs:
.LFB25:
	.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
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	h(%rip), %eax
	movq	%rdi, 16(%rsp)
	movl	%esi, 24(%rsp)
	movb	%dl, 15(%rsp)
	movl	%eax, 8(%rsp)
	testl	%eax, %eax
	jle	.L20
	movslq	w(%rip), %rbp
	testl	%ebp, %ebp
	jle	.L5
	leal	-1(%rax), %ebx
	leaq	visited(%rip), %rcx
	salq	$2, %rbp
	imulq	$4000, %rbx, %rbx
	leaq	4000(%rcx), %rax
	addq	%rax, %rbx
	.p2align 4,,10
	.p2align 3
.L7:
	movq	%rcx, %rdi
	movq	%rbp, %rdx
	xorl	%esi, %esi
	call	memset@PLT
	movq	%rax, %rcx
	addq	$4000, %rcx
	cmpq	%rcx, %rbx
	jne	.L7
.L20:
	movl	w(%rip), %ebp
.L5:
	movq	16(%rsp), %xmm0
	movl	24(%rsp), %r8d
	movl	$1, %edx
	xorl	%eax, %eax
	movl	$1, tail(%rip)
	movd	16(%rsp), %xmm1
	leaq	p(%rip), %r14
	leaq	map(%rip), %r11
	movl	%r8d, 8+Q(%rip)
	movd	20(%rsp), %xmm2
	leaq	visited(%rip), %r13
	leaq	Q(%rip), %r12
	movq	%xmm0, Q(%rip)
	jmp	.L15
	.p2align 4,,10
	.p2align 3
.L9:
	movslq	%r10d, %rbx
	imulq	$1000, %rbx, %rbx
	leaq	(%r11,%rbx), %r15
	cmpb	$88, (%r15,%r9)
	je	.L11
	addq	%r9, %rbx
	movl	0(%r13,%rbx,4), %r15d
	testl	%r15d, %r15d
	jne	.L11
	movl	$1, 0(%r13,%rbx,4)
	movq	(%r14), %r15
	movq	%r15, next(%rip)
	movl	8+p(%rip), %r15d
	movl	%r10d, next(%rip)
	movslq	%edx, %r10
	leaq	(%r10,%r10,2), %r10
	movl	%r15d, 8+next(%rip)
	movl	%r8d, 8(%r12,%r10,4)
	movq	%xmm0, (%r12,%r10,4)
	leal	1(%rdx), %r10d
	movslq	%r10d, %rdx
	movl	%r10d, %r15d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r15d
	sarq	$44, %rdx
	subl	%r15d, %edx
	imull	$10000, %edx, %r15d
	movl	%r10d, %edx
	subl	%r15d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L10:
	testl	%esi, %esi
	jle	.L12
	subl	$1, %esi
	movslq	%esi, %r10
	movd	%esi, %xmm0
	imulq	$1000, %r10, %r10
	punpckldq	%xmm2, %xmm0
	leaq	(%r11,%r10), %rbx
	cmpb	$88, (%rbx,%r9)
	je	.L12
	addq	%r9, %r10
	movl	0(%r13,%r10,4), %ebx
	testl	%ebx, %ebx
	jne	.L12
	movl	$1, 0(%r13,%r10,4)
	movq	(%r14), %r9
	movq	%r9, next(%rip)
	movl	8+p(%rip), %r9d
	movl	%esi, next(%rip)
	movslq	%edx, %rsi
	leaq	(%rsi,%rsi,2), %rsi
	movl	%r9d, 8+next(%rip)
	movl	%r8d, 8(%r12,%rsi,4)
	movq	%xmm0, (%r12,%rsi,4)
	leal	1(%rdx), %esi
	movslq	%esi, %rdx
	movl	%esi, %r9d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r9d
	sarq	$44, %rdx
	subl	%r9d, %edx
	imull	$10000, %edx, %r9d
	movl	%esi, %edx
	subl	%r9d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L12:
	leal	1(%rcx), %esi
	movdqa	%xmm1, %xmm0
	movd	%esi, %xmm4
	punpckldq	%xmm4, %xmm0
	cmpl	%ebp, %esi
	jge	.L13
	imulq	$1000, %rdi, %r10
	movslq	%esi, %r9
	leaq	(%r11,%r10), %rbx
	cmpb	$88, (%rbx,%r9)
	je	.L13
	addq	%r10, %r9
	movl	0(%r13,%r9,4), %r10d
	testl	%r10d, %r10d
	jne	.L13
	movl	$1, 0(%r13,%r9,4)
	movq	(%r14), %r10
	movq	%r10, next(%rip)
	movl	8+p(%rip), %r10d
	movl	%esi, 4+next(%rip)
	movslq	%edx, %rsi
	leaq	(%rsi,%rsi,2), %rsi
	movl	%r10d, 8+next(%rip)
	movl	%r8d, 8(%r12,%rsi,4)
	movq	%xmm0, (%r12,%rsi,4)
	leal	1(%rdx), %esi
	movslq	%esi, %rdx
	movl	%esi, %r10d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r10d
	sarq	$44, %rdx
	subl	%r10d, %edx
	imull	$10000, %edx, %r10d
	movl	%esi, %edx
	subl	%r10d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L13:
	testl	%ecx, %ecx
	jle	.L14
	imulq	$1000, %rdi, %rdi
	subl	$1, %ecx
	movslq	%ecx, %rsi
	movd	%ecx, %xmm5
	punpckldq	%xmm5, %xmm1
	leaq	(%r11,%rdi), %r9
	cmpb	$88, (%r9,%rsi)
	je	.L14
	addq	%rsi, %rdi
	movl	0(%r13,%rdi,4), %esi
	testl	%esi, %esi
	jne	.L14
	movl	$1, 0(%r13,%rdi,4)
	movq	(%r14), %rsi
	movq	%rsi, next(%rip)
	movl	8+p(%rip), %esi
	movl	%ecx, 4+next(%rip)
	movslq	%edx, %rcx
	leaq	(%rcx,%rcx,2), %rcx
	movl	%esi, 8+next(%rip)
	movl	%r8d, 8(%r12,%rcx,4)
	movq	%xmm1, (%r12,%rcx,4)
	leal	1(%rdx), %ecx
	movslq	%ecx, %rdx
	movl	%ecx, %esi
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %esi
	sarq	$44, %rdx
	subl	%esi, %edx
	imull	$10000, %edx, %esi
	movl	%ecx, %edx
	subl	%esi, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L14:
	cmpl	%edx, %eax
	je	.L4
	movslq	%eax, %rcx
	leaq	4+Q(%rip), %rbx
	leaq	(%rcx,%rcx,2), %rcx
	salq	$2, %rcx
	movq	-4(%rbx,%rcx), %xmm0
	addq	%r12, %rcx
	movd	4(%rcx), %xmm2
	movd	(%rcx), %xmm1
	movl	8(%rcx), %r8d
.L15:
	leal	1(%rax), %edi
	movd	%xmm0, %esi
	pshufd	$0xe5, %xmm0, %xmm3
	movd	%xmm3, %ecx
	movslq	%edi, %rax
	movl	%edi, %r9d
	movzbl	15(%rsp), %ebx
	movq	%xmm0, (%r14)
	imulq	$1759218605, %rax, %rax
	sarl	$31, %r9d
	movl	%r8d, 8+p(%rip)
	sarq	$44, %rax
	subl	%r9d, %eax
	imull	$10000, %eax, %r9d
	movl	%edi, %eax
	movslq	%esi, %rdi
	imulq	$1000, %rdi, %r10
	subl	%r9d, %eax
	movslq	%ecx, %r9
	addq	%r11, %r10
	movl	%eax, head(%rip)
	cmpb	%bl, (%r10,%r9)
	je	.L4
	leal	1(%rsi), %r10d
	addl	$1, %r8d
	movd	%r10d, %xmm0
	movl	%r8d, 8+p(%rip)
	punpckldq	%xmm2, %xmm0
	cmpl	8(%rsp), %r10d
	jl	.L9
.L11:
	movl	tail(%rip), %edx
	jmp	.L10
	.p2align 4,,10
	.p2align 3
.L4:
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	movl	%r8d, %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
	.cfi_endproc
.LFE25:
	.size	bfs, .-bfs
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d %d %d"
.LC1:
	.string	"%s"
.LC2:
	.string	"%d\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB26:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	w(%rip), %rdx
	leaq	n(%rip), %rcx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	leaq	h(%rip), %rsi
	leaq	.LC0(%rip), %rdi
	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	.LC1(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	leaq	map(%rip), %rbx
	subq	$2040, %rsp
	.cfi_def_cfa_offset 2096
	movq	%fs:40, %rax
	movq	%rax, 2024(%rsp)
	xorl	%eax, %eax
	leaq	16(%rsp), %rbp
	call	__isoc99_scanf@PLT
	movl	h(%rip), %edx
	testl	%edx, %edx
	jle	.L34
	.p2align 4,,10
	.p2align 3
.L33:
	movq	%rbp, %rsi
	movq	%r12, %rdi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movslq	w(%rip), %rsi
	xorl	%eax, %eax
	xorl	%edi, %edi
	testl	%esi, %esi
	jle	.L26
	.p2align 4,,10
	.p2align 3
.L31:
	movzbl	0(%rbp,%rax), %edx
	movl	%eax, %ecx
	cmpb	$83, %dl
	je	.L27
	movb	%dl, (%rbx,%rax)
	addq	$1, %rax
	cmpq	%rsi, %rax
	jne	.L31
	movl	%r15d, %ecx
	testb	%dil, %dil
	je	.L26
.L30:
	movl	%ecx, 8(%rsp)
	movl	%r14d, 4(%rsp)
.L26:
	addl	$1, %r13d
	addq	$1000, %rbx
	cmpl	%r13d, h(%rip)
	jg	.L33
.L34:
	movl	n(%rip), %eax
	movl	$1, %ebx
	xorl	%r12d, %r12d
	leaq	p(%rip), %rbp
	testl	%eax, %eax
	jle	.L24
	.p2align 4,,10
	.p2align 3
.L23:
	leal	48(%rbx), %edx
	movq	4(%rsp), %rdi
	xorl	%esi, %esi
	addl	$1, %ebx
	movsbl	%dl, %edx
	call	bfs
	addl	%eax, %r12d
	movq	0(%rbp), %rax
	movq	%rax, 4(%rsp)
	movsbl	%bl, %eax
	cmpl	n(%rip), %eax
	jle	.L23
.L24:
	xorl	%eax, %eax
	movl	%r12d, %edx
	movl	$1, %edi
	leaq	.LC2(%rip), %rsi
	call	__printf_chk@PLT
	movq	2024(%rsp), %rax
	subq	%fs:40, %rax
	jne	.L49
	addq	$2040, %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
	.p2align 4,,10
	.p2align 3
.L27:
	.cfi_restore_state
	movb	$83, (%rbx,%rax)
	addq	$1, %rax
	cmpq	%rsi, %rax
	je	.L37
	movl	%ecx, %r15d
	movl	%r13d, %r14d
	movl	$1, %edi
	jmp	.L31
	.p2align 4,,10
	.p2align 3
.L37:
	movl	%r13d, %r14d
	jmp	.L30
.L49:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE26:
	.size	main, .-main
	.globl	visited
	.bss
	.align 32
	.type	visited, @object
	.size	visited, 4000000
visited:
	.zero	4000000
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	w
	.align 4
	.type	w, @object
	.size	w, 4
w:
	.zero	4
	.globl	h
	.align 4
	.type	h, @object
	.size	h, 4
h:
	.zero	4
	.globl	next
	.align 8
	.type	next, @object
	.size	next, 12
next:
	.zero	12
	.globl	p
	.align 8
	.type	p, @object
	.size	p, 12
p:
	.zero	12
	.globl	map
	.align 32
	.type	map, @object
	.size	map, 1000000
map:
	.zero	1000000
	.globl	tail
	.align 4
	.type	tail, @object
	.size	tail, 4
tail:
	.zero	4
	.globl	head
	.align 4
	.type	head, @object
	.size	head, 4
head:
	.zero	4
	.globl	Q
	.align 32
	.type	Q, @object
	.size	Q, 120000
Q:
	.zero	120000
	.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
	.globl	enqueue
	.type	enqueue, @function
enqueue:
.LFB23:
	.cfi_startproc
	endbr64
	movslq	tail(%rip), %rax
	leaq	(%rax,%rax,2), %rcx
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	leaq	(%rax,%rcx,4), %rax
	addl	$1, %edx
	movq	%rdi, (%rax)
	movl	%edx, %ecx
	movl	%esi, 8(%rax)
	movslq	%edx, %rax
	sarl	$31, %ecx
	imulq	$1759218605, %rax, %rax
	sarq	$44, %rax
	subl	%ecx, %eax
	imull	$10000, %eax, %eax
	subl	%eax, %edx
	movl	%edx, tail(%rip)
	ret
	.cfi_endproc
.LFE23:
	.size	enqueue, .-enqueue
	.p2align 4
	.globl	dequeue
	.type	dequeue, @function
dequeue:
.LFB24:
	.cfi_startproc
	endbr64
	movslq	head(%rip), %rax
	leaq	Q(%rip), %rsi
	movq	%rax, %rdx
	leaq	(%rax,%rax,2), %rcx
	addl	$1, %edx
	salq	$2, %rcx
	movslq	%edx, %rax
	movl	%edx, %edi
	imulq	$1759218605, %rax, %rax
	sarl	$31, %edi
	sarq	$44, %rax
	subl	%edi, %eax
	imull	$10000, %eax, %eax
	subl	%eax, %edx
	movl	%edx, head(%rip)
	movl	8(%rsi,%rcx), %edx
	movq	(%rsi,%rcx), %rax
	ret
	.cfi_endproc
.LFE24:
	.size	dequeue, .-dequeue
	.p2align 4
	.globl	bfs
	.type	bfs, @function
bfs:
.LFB25:
	.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
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$40, %rsp
	.cfi_def_cfa_offset 96
	movl	h(%rip), %eax
	movq	%rdi, 16(%rsp)
	movl	%esi, 24(%rsp)
	movb	%dl, 15(%rsp)
	movl	%eax, 8(%rsp)
	testl	%eax, %eax
	jle	.L20
	movslq	w(%rip), %rbp
	testl	%ebp, %ebp
	jle	.L5
	leal	-1(%rax), %ebx
	leaq	visited(%rip), %rcx
	salq	$2, %rbp
	imulq	$4000, %rbx, %rbx
	leaq	4000(%rcx), %rax
	addq	%rax, %rbx
	.p2align 4,,10
	.p2align 3
.L7:
	movq	%rcx, %rdi
	movq	%rbp, %rdx
	xorl	%esi, %esi
	call	memset@PLT
	movq	%rax, %rcx
	addq	$4000, %rcx
	cmpq	%rcx, %rbx
	jne	.L7
.L20:
	movl	w(%rip), %ebp
.L5:
	movq	16(%rsp), %xmm0
	movl	24(%rsp), %r8d
	movl	$1, %edx
	xorl	%eax, %eax
	movl	$1, tail(%rip)
	movd	16(%rsp), %xmm1
	leaq	p(%rip), %r14
	leaq	map(%rip), %r11
	movl	%r8d, 8+Q(%rip)
	movd	20(%rsp), %xmm2
	leaq	visited(%rip), %r13
	leaq	Q(%rip), %r12
	movq	%xmm0, Q(%rip)
	jmp	.L15
	.p2align 4,,10
	.p2align 3
.L9:
	movslq	%r10d, %rbx
	imulq	$1000, %rbx, %rbx
	leaq	(%r11,%rbx), %r15
	cmpb	$88, (%r15,%r9)
	je	.L11
	addq	%r9, %rbx
	movl	0(%r13,%rbx,4), %r15d
	testl	%r15d, %r15d
	jne	.L11
	movl	$1, 0(%r13,%rbx,4)
	movq	(%r14), %r15
	movq	%r15, next(%rip)
	movl	8+p(%rip), %r15d
	movl	%r10d, next(%rip)
	movslq	%edx, %r10
	leaq	(%r10,%r10,2), %r10
	movl	%r15d, 8+next(%rip)
	movl	%r8d, 8(%r12,%r10,4)
	movq	%xmm0, (%r12,%r10,4)
	leal	1(%rdx), %r10d
	movslq	%r10d, %rdx
	movl	%r10d, %r15d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r15d
	sarq	$44, %rdx
	subl	%r15d, %edx
	imull	$10000, %edx, %r15d
	movl	%r10d, %edx
	subl	%r15d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L10:
	testl	%esi, %esi
	jle	.L12
	subl	$1, %esi
	movslq	%esi, %r10
	movd	%esi, %xmm0
	imulq	$1000, %r10, %r10
	punpckldq	%xmm2, %xmm0
	leaq	(%r11,%r10), %rbx
	cmpb	$88, (%rbx,%r9)
	je	.L12
	addq	%r9, %r10
	movl	0(%r13,%r10,4), %ebx
	testl	%ebx, %ebx
	jne	.L12
	movl	$1, 0(%r13,%r10,4)
	movq	(%r14), %r9
	movq	%r9, next(%rip)
	movl	8+p(%rip), %r9d
	movl	%esi, next(%rip)
	movslq	%edx, %rsi
	leaq	(%rsi,%rsi,2), %rsi
	movl	%r9d, 8+next(%rip)
	movl	%r8d, 8(%r12,%rsi,4)
	movq	%xmm0, (%r12,%rsi,4)
	leal	1(%rdx), %esi
	movslq	%esi, %rdx
	movl	%esi, %r9d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r9d
	sarq	$44, %rdx
	subl	%r9d, %edx
	imull	$10000, %edx, %r9d
	movl	%esi, %edx
	subl	%r9d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L12:
	leal	1(%rcx), %esi
	movdqa	%xmm1, %xmm0
	movd	%esi, %xmm4
	punpckldq	%xmm4, %xmm0
	cmpl	%ebp, %esi
	jge	.L13
	imulq	$1000, %rdi, %r10
	movslq	%esi, %r9
	leaq	(%r11,%r10), %rbx
	cmpb	$88, (%rbx,%r9)
	je	.L13
	addq	%r10, %r9
	movl	0(%r13,%r9,4), %r10d
	testl	%r10d, %r10d
	jne	.L13
	movl	$1, 0(%r13,%r9,4)
	movq	(%r14), %r10
	movq	%r10, next(%rip)
	movl	8+p(%rip), %r10d
	movl	%esi, 4+next(%rip)
	movslq	%edx, %rsi
	leaq	(%rsi,%rsi,2), %rsi
	movl	%r10d, 8+next(%rip)
	movl	%r8d, 8(%r12,%rsi,4)
	movq	%xmm0, (%r12,%rsi,4)
	leal	1(%rdx), %esi
	movslq	%esi, %rdx
	movl	%esi, %r10d
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %r10d
	sarq	$44, %rdx
	subl	%r10d, %edx
	imull	$10000, %edx, %r10d
	movl	%esi, %edx
	subl	%r10d, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L13:
	testl	%ecx, %ecx
	jle	.L14
	imulq	$1000, %rdi, %rdi
	subl	$1, %ecx
	movslq	%ecx, %rsi
	movd	%ecx, %xmm5
	punpckldq	%xmm5, %xmm1
	leaq	(%r11,%rdi), %r9
	cmpb	$88, (%r9,%rsi)
	je	.L14
	addq	%rsi, %rdi
	movl	0(%r13,%rdi,4), %esi
	testl	%esi, %esi
	jne	.L14
	movl	$1, 0(%r13,%rdi,4)
	movq	(%r14), %rsi
	movq	%rsi, next(%rip)
	movl	8+p(%rip), %esi
	movl	%ecx, 4+next(%rip)
	movslq	%edx, %rcx
	leaq	(%rcx,%rcx,2), %rcx
	movl	%esi, 8+next(%rip)
	movl	%r8d, 8(%r12,%rcx,4)
	movq	%xmm1, (%r12,%rcx,4)
	leal	1(%rdx), %ecx
	movslq	%ecx, %rdx
	movl	%ecx, %esi
	imulq	$1759218605, %rdx, %rdx
	sarl	$31, %esi
	sarq	$44, %rdx
	subl	%esi, %edx
	imull	$10000, %edx, %esi
	movl	%ecx, %edx
	subl	%esi, %edx
	movl	%edx, tail(%rip)
	.p2align 4,,10
	.p2align 3
.L14:
	cmpl	%edx, %eax
	je	.L4
	movslq	%eax, %rcx
	leaq	4+Q(%rip), %rbx
	leaq	(%rcx,%rcx,2), %rcx
	salq	$2, %rcx
	movq	-4(%rbx,%rcx), %xmm0
	addq	%r12, %rcx
	movd	4(%rcx), %xmm2
	movd	(%rcx), %xmm1
	movl	8(%rcx), %r8d
.L15:
	leal	1(%rax), %edi
	movd	%xmm0, %esi
	pshufd	$0xe5, %xmm0, %xmm3
	movd	%xmm3, %ecx
	movslq	%edi, %rax
	movl	%edi, %r9d
	movzbl	15(%rsp), %ebx
	movq	%xmm0, (%r14)
	imulq	$1759218605, %rax, %rax
	sarl	$31, %r9d
	movl	%r8d, 8+p(%rip)
	sarq	$44, %rax
	subl	%r9d, %eax
	imull	$10000, %eax, %r9d
	movl	%edi, %eax
	movslq	%esi, %rdi
	imulq	$1000, %rdi, %r10
	subl	%r9d, %eax
	movslq	%ecx, %r9
	addq	%r11, %r10
	movl	%eax, head(%rip)
	cmpb	%bl, (%r10,%r9)
	je	.L4
	leal	1(%rsi), %r10d
	addl	$1, %r8d
	movd	%r10d, %xmm0
	movl	%r8d, 8+p(%rip)
	punpckldq	%xmm2, %xmm0
	cmpl	8(%rsp), %r10d
	jl	.L9
.L11:
	movl	tail(%rip), %edx
	jmp	.L10
	.p2align 4,,10
	.p2align 3
.L4:
	addq	$40, %rsp
	.cfi_def_cfa_offset 56
	movl	%r8d, %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
	.cfi_endproc
.LFE25:
	.size	bfs, .-bfs
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d %d %d"
.LC1:
	.string	"%s"
.LC2:
	.string	"%d\n"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB26:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	w(%rip), %rdx
	leaq	n(%rip), %rcx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	leaq	h(%rip), %rsi
	leaq	.LC0(%rip), %rdi
	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	.LC1(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	leaq	map(%rip), %rbx
	subq	$2040, %rsp
	.cfi_def_cfa_offset 2096
	movq	%fs:40, %rax
	movq	%rax, 2024(%rsp)
	xorl	%eax, %eax
	leaq	16(%rsp), %rbp
	call	__isoc99_scanf@PLT
	movl	h(%rip), %edx
	testl	%edx, %edx
	jle	.L34
	.p2align 4,,10
	.p2align 3
.L33:
	movq	%rbp, %rsi
	movq	%r12, %rdi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movslq	w(%rip), %rsi
	xorl	%eax, %eax
	xorl	%edi, %edi
	testl	%esi, %esi
	jle	.L26
	.p2align 4,,10
	.p2align 3
.L31:
	movzbl	0(%rbp,%rax), %edx
	movl	%eax, %ecx
	cmpb	$83, %dl
	je	.L27
	movb	%dl, (%rbx,%rax)
	addq	$1, %rax
	cmpq	%rsi, %rax
	jne	.L31
	movl	%r15d, %ecx
	testb	%dil, %dil
	je	.L26
.L30:
	movl	%ecx, 8(%rsp)
	movl	%r14d, 4(%rsp)
.L26:
	addl	$1, %r13d
	addq	$1000, %rbx
	cmpl	%r13d, h(%rip)
	jg	.L33
.L34:
	movl	n(%rip), %eax
	movl	$1, %ebx
	xorl	%r12d, %r12d
	leaq	p(%rip), %rbp
	testl	%eax, %eax
	jle	.L24
	.p2align 4,,10
	.p2align 3
.L23:
	leal	48(%rbx), %edx
	movq	4(%rsp), %rdi
	xorl	%esi, %esi
	addl	$1, %ebx
	movsbl	%dl, %edx
	call	bfs
	addl	%eax, %r12d
	movq	0(%rbp), %rax
	movq	%rax, 4(%rsp)
	movsbl	%bl, %eax
	cmpl	n(%rip), %eax
	jle	.L23
.L24:
	xorl	%eax, %eax
	movl	%r12d, %edx
	movl	$1, %edi
	leaq	.LC2(%rip), %rsi
	call	__printf_chk@PLT
	movq	2024(%rsp), %rax
	subq	%fs:40, %rax
	jne	.L49
	addq	$2040, %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
	.p2align 4,,10
	.p2align 3
.L27:
	.cfi_restore_state
	movb	$83, (%rbx,%rax)
	addq	$1, %rax
	cmpq	%rsi, %rax
	je	.L37
	movl	%ecx, %r15d
	movl	%r13d, %r14d
	movl	$1, %edi
	jmp	.L31
	.p2align 4,,10
	.p2align 3
.L37:
	movl	%r13d, %r14d
	jmp	.L30
.L49:
	call	__stack_chk_fail@PLT
	.cfi_endproc
.LFE26:
	.size	main, .-main
	.globl	visited
	.bss
	.align 32
	.type	visited, @object
	.size	visited, 4000000
visited:
	.zero	4000000
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	w
	.align 4
	.type	w, @object
	.size	w, 4
w:
	.zero	4
	.globl	h
	.align 4
	.type	h, @object
	.size	h, 4
h:
	.zero	4
	.globl	next
	.align 8
	.type	next, @object
	.size	next, 12
next:
	.zero	12
	.globl	p
	.align 8
	.type	p, @object
	.size	p, 12
p:
	.zero	12
	.globl	map
	.align 32
	.type	map, @object
	.size	map, 1000000
map:
	.zero	1000000
	.globl	tail
	.align 4
	.type	tail, @object
	.size	tail, 4
tail:
	.zero	4
	.globl	head
	.align 4
	.type	head, @object
	.size	head, 4
head:
	.zero	4
	.globl	Q
	.align 32
	.type	Q, @object
	.size	Q, 120000
Q:
	.zero	120000
	.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>

typedef struct{
  int x,y,t;
}Point;

Point Q[10000];
int head,tail;
char map[1000][1000];
Point p,next;
int h,w,n;
int visited[1000][1000];
  

void enqueue(Point n){
  Q[tail] = n;
  tail = (tail+1)%10000;
}

Point  dequeue(){
  Point re;
  re = Q[head];
  head = (head+1)%10000;
  return re;
}


int bfs(Point start,char end){
  int i,j;
  for(i=0;i<h;i++)
    for(j=0;j<w;j++)
      visited[i][j]=0;

  head = 0;
  tail = 0;
  enqueue(start);
  while(head != tail){
    p = dequeue();

    if(map[p.x][p.y] == end) break;
    else  p.t++;

    if(p.x+1 < h &&  map[p.x+1][p.y] != 'X' && visited[p.x+1][p.y]==0){
      next=p;
      next.x++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.x-1 >= 0 && map[p.x-1][p.y] != 'X' && visited[p.x-1][p.y]==0){
      next=p;
      next.x--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y+1 < w && map[p.x][p.y+1] != 'X' && visited[p.x][p.y+1]==0){
      next=p;
      next.y++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y-1 >= 0 && map[p.x][p.y-1] != 'X' && visited[p.x][p.y-1]==0){
      next=p;
      next.y--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
  }
  return p.t;
}
  

int main (){
  int i,j,k;
  int time;
  char hp,str[2000];
  Point start;

  scanf("%d %d %d",&h,&w,&n);
  for(i=0;i<h;i++){
    scanf("%s",str);
    for(j=0;j<w;j++){
      map[i][j] = str[j];
      if(map[i][j] == 'S'){
	start.x = i;
	start.y = j;
      }
    }
  }
  /*
  printf("\n");
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      printf("%c",map[i][j]);
    }
    printf("\n");
  }
  */
  hp=1;
  time = 0;

  while(hp<=n){
    start.t=0;
    time += bfs(start,'0'+hp);
    hp++;
    start = p;
  }
  printf("%d\n",time);

  return 0;
}
3 3 1
S..
...
..1

4

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>

typedef struct{
  int x,y,t;
}Point;

Point Q[10000];
int head,tail;
char map[1000][1000];
Point p,next;
int h,w,n;
int visited[1000][1000];
  

void enqueue(Point n){
  Q[tail] = n;
  tail = (tail+1)%10000;
}

Point  dequeue(){
  Point re;
  re = Q[head];
  head = (head+1)%10000;
  return re;
}


int bfs(Point start,char end){
  int i,j;
  for(i=0;i<h;i++)
    for(j=0;j<w;j++)
      visited[i][j]=0;

  head = 0;
  tail = 0;
  enqueue(start);
  while(head != tail){
    p = dequeue();

    if(map[p.x][p.y] == end) break;
    else  p.t++;

    if(p.x+1 < h &&  map[p.x+1][p.y] != 'X' && visited[p.x+1][p.y]==0){
      next=p;
      next.x++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.x-1 >= 0 && map[p.x-1][p.y] != 'X' && visited[p.x-1][p.y]==0){
      next=p;
      next.x--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y+1 < w && map[p.x][p.y+1] != 'X' && visited[p.x][p.y+1]==0){
      next=p;
      next.y++;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
    if(p.y-1 >= 0 && map[p.x][p.y-1] != 'X' && visited[p.x][p.y-1]==0){
      next=p;
      next.y--;
      enqueue(next);
      visited[next.x][next.y]=1;
    }
  }
  return p.t;
}
  

int main (){
  int i,j,k;
  int time;
  char hp,str[2000];
  Point start;

  scanf("%d %d %d",&h,&w,&n);
  for(i=0;i<h;i++){
    scanf("%s",str);
    for(j=0;j<w;j++){
      map[i][j] = str[j];
      if(map[i][j] == 'S'){
	start.x = i;
	start.y = j;
      }
    }
  }
  /*
  printf("\n");
  for(i=0;i<h;i++){
    for(j=0;j<w;j++){
      printf("%c",map[i][j]);
    }
    printf("\n");
  }
  */
  hp=1;
  time = 0;

  while(hp<=n){
    start.t=0;
    time += bfs(start,'0'+hp);
    hp++;
    start = p;
  }
  printf("%d\n",time);

  return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	Q
	.bss
	.align 32
	.type	Q, @object
	.size	Q, 120000
Q:
	.zero	120000
	.globl	head
	.align 4
	.type	head, @object
	.size	head, 4
head:
	.zero	4
	.globl	tail
	.align 4
	.type	tail, @object
	.size	tail, 4
tail:
	.zero	4
	.globl	map
	.align 32
	.type	map, @object
	.size	map, 1000000
map:
	.zero	1000000
	.globl	p
	.align 8
	.type	p, @object
	.size	p, 12
p:
	.zero	12
	.globl	next
	.align 8
	.type	next, @object
	.size	next, 12
next:
	.zero	12
	.globl	h
	.align 4
	.type	h, @object
	.size	h, 4
h:
	.zero	4
	.globl	w
	.align 4
	.type	w, @object
	.size	w, 4
w:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	visited
	.align 32
	.type	visited, @object
	.size	visited, 4000000
visited:
	.zero	4000000
	.text
	.globl	enqueue
	.type	enqueue, @function
enqueue:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, %rdx
	movl	%esi, %eax
	movq	%rdx, -16(%rbp)
	movl	%eax, -8(%rbp)
	movl	tail(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	-16(%rbp), %rcx
	movq	%rcx, (%rdx,%rax)
	movl	-8(%rbp), %ecx
	movl	%ecx, 8(%rdx,%rax)
	movl	tail(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, tail(%rip)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	enqueue, .-enqueue
	.globl	dequeue
	.type	dequeue, @function
dequeue:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	head(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	(%rdx,%rax), %rcx
	movq	%rcx, -24(%rbp)
	movl	8(%rdx,%rax), %eax
	movl	%eax, -16(%rbp)
	movl	head(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, head(%rip)
	movq	-24(%rbp), %rax
	movq	%rax, -12(%rbp)
	movl	-16(%rbp), %eax
	movl	%eax, -4(%rbp)
	movq	-12(%rbp), %rax
	movl	-4(%rbp), %ecx
	movq	%rcx, %rdx
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	dequeue, .-dequeue
	.globl	bfs
	.type	bfs, @function
bfs:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$48, %rsp
	movq	%rdi, %rcx
	movl	%esi, %eax
	movq	%rcx, -32(%rbp)
	movl	%eax, -24(%rbp)
	movl	%edx, %eax
	movb	%al, -36(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L5
.L8:
	movl	$0, -4(%rbp)
	jmp	.L6
.L7:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$0, (%rdx,%rax)
	addl	$1, -4(%rbp)
.L6:
	movl	w(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L7
	addl	$1, -8(%rbp)
.L5:
	movl	h(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L8
	movl	$0, head(%rip)
	movl	$0, tail(%rip)
	movq	-32(%rbp), %rdx
	movl	-24(%rbp), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	jmp	.L9
.L15:
	movl	$0, %eax
	call	dequeue
	movq	%rax, p(%rip)
	movl	8+p(%rip), %eax
	andl	$0, %eax
	orl	%edx, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	%al, -36(%rbp)
	je	.L17
	movl	8+p(%rip), %eax
	addl	$1, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	h(%rip), %eax
	cmpl	%eax, %edx
	jge	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L12
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	addl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L12:
	movl	p(%rip), %eax
	testl	%eax, %eax
	jle	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L13
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	subl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L13:
	movl	4+p(%rip), %eax
	leal	1(%rax), %edx
	movl	w(%rip), %eax
	cmpl	%eax, %edx
	jge	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L14
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	addl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L14:
	movl	4+p(%rip), %eax
	testl	%eax, %eax
	jle	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L9
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	subl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L9:
	movl	head(%rip), %edx
	movl	tail(%rip), %eax
	cmpl	%eax, %edx
	jne	.L15
	jmp	.L11
.L17:
	nop
.L11:
	movl	8+p(%rip), %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	bfs, .-bfs
	.section	.rodata
.LC0:
	.string	"%d %d %d"
.LC1:
	.string	"%s"
.LC2:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB3:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$2048, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	leaq	n(%rip), %rax
	movq	%rax, %rcx
	leaq	w(%rip), %rax
	movq	%rax, %rdx
	leaq	h(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2040(%rbp)
	jmp	.L19
.L23:
	leaq	-2016(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2036(%rbp)
	jmp	.L20
.L22:
	movl	-2036(%rbp), %eax
	cltq
	movzbl	-2016(%rbp,%rax), %eax
	movl	-2036(%rbp), %edx
	movslq	%edx, %rcx
	movl	-2040(%rbp), %edx
	movslq	%edx, %rdx
	imulq	$1000, %rdx, %rdx
	addq	%rdx, %rcx
	leaq	map(%rip), %rdx
	addq	%rcx, %rdx
	movb	%al, (%rdx)
	movl	-2036(%rbp), %eax
	movslq	%eax, %rdx
	movl	-2040(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$83, %al
	jne	.L21
	movl	-2040(%rbp), %eax
	movl	%eax, -2028(%rbp)
	movl	-2036(%rbp), %eax
	movl	%eax, -2024(%rbp)
.L21:
	addl	$1, -2036(%rbp)
.L20:
	movl	w(%rip), %eax
	cmpl	%eax, -2036(%rbp)
	jl	.L22
	addl	$1, -2040(%rbp)
.L19:
	movl	h(%rip), %eax
	cmpl	%eax, -2040(%rbp)
	jl	.L23
	movb	$1, -2041(%rbp)
	movl	$0, -2032(%rbp)
	jmp	.L24
.L25:
	movl	$0, -2020(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$48, %eax
	movsbl	%al, %edx
	movq	-2028(%rbp), %rcx
	movl	-2020(%rbp), %eax
	movq	%rcx, %rdi
	movl	%eax, %esi
	call	bfs
	addl	%eax, -2032(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$1, %eax
	movb	%al, -2041(%rbp)
	movq	p(%rip), %rax
	movq	%rax, -2028(%rbp)
	movl	8+p(%rip), %eax
	movl	%eax, -2020(%rbp)
.L24:
	movsbl	-2041(%rbp), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jle	.L25
	movl	-2032(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L27
	call	__stack_chk_fail@PLT
.L27:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE3:
	.size	main, .-main
	.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	Q
	.bss
	.align 32
	.type	Q, @object
	.size	Q, 120000
Q:
	.zero	120000
	.globl	head
	.align 4
	.type	head, @object
	.size	head, 4
head:
	.zero	4
	.globl	tail
	.align 4
	.type	tail, @object
	.size	tail, 4
tail:
	.zero	4
	.globl	map
	.align 32
	.type	map, @object
	.size	map, 1000000
map:
	.zero	1000000
	.globl	p
	.align 8
	.type	p, @object
	.size	p, 12
p:
	.zero	12
	.globl	next
	.align 8
	.type	next, @object
	.size	next, 12
next:
	.zero	12
	.globl	h
	.align 4
	.type	h, @object
	.size	h, 4
h:
	.zero	4
	.globl	w
	.align 4
	.type	w, @object
	.size	w, 4
w:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	visited
	.align 32
	.type	visited, @object
	.size	visited, 4000000
visited:
	.zero	4000000
	.text
	.globl	enqueue
	.type	enqueue, @function
enqueue:
.LFB0:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movq	%rdi, %rdx
	movl	%esi, %eax
	movq	%rdx, -16(%rbp)
	movl	%eax, -8(%rbp)
	movl	tail(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	-16(%rbp), %rcx
	movq	%rcx, (%rdx,%rax)
	movl	-8(%rbp), %ecx
	movl	%ecx, 8(%rdx,%rax)
	movl	tail(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, tail(%rip)
	nop
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE0:
	.size	enqueue, .-enqueue
	.globl	dequeue
	.type	dequeue, @function
dequeue:
.LFB1:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	movl	head(%rip), %eax
	movslq	%eax, %rdx
	movq	%rdx, %rax
	addq	%rax, %rax
	addq	%rdx, %rax
	salq	$2, %rax
	movq	%rax, %rdx
	leaq	Q(%rip), %rax
	movq	(%rdx,%rax), %rcx
	movq	%rcx, -24(%rbp)
	movl	8(%rdx,%rax), %eax
	movl	%eax, -16(%rbp)
	movl	head(%rip), %eax
	leal	1(%rax), %edx
	movslq	%edx, %rax
	imulq	$1759218605, %rax, %rax
	shrq	$32, %rax
	sarl	$12, %eax
	movl	%edx, %ecx
	sarl	$31, %ecx
	subl	%ecx, %eax
	imull	$10000, %eax, %ecx
	movl	%edx, %eax
	subl	%ecx, %eax
	movl	%eax, head(%rip)
	movq	-24(%rbp), %rax
	movq	%rax, -12(%rbp)
	movl	-16(%rbp), %eax
	movl	%eax, -4(%rbp)
	movq	-12(%rbp), %rax
	movl	-4(%rbp), %ecx
	movq	%rcx, %rdx
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE1:
	.size	dequeue, .-dequeue
	.globl	bfs
	.type	bfs, @function
bfs:
.LFB2:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$48, %rsp
	movq	%rdi, %rcx
	movl	%esi, %eax
	movq	%rcx, -32(%rbp)
	movl	%eax, -24(%rbp)
	movl	%edx, %eax
	movb	%al, -36(%rbp)
	movl	$0, -8(%rbp)
	jmp	.L5
.L8:
	movl	$0, -4(%rbp)
	jmp	.L6
.L7:
	movl	-4(%rbp), %eax
	movslq	%eax, %rdx
	movl	-8(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$0, (%rdx,%rax)
	addl	$1, -4(%rbp)
.L6:
	movl	w(%rip), %eax
	cmpl	%eax, -4(%rbp)
	jl	.L7
	addl	$1, -8(%rbp)
.L5:
	movl	h(%rip), %eax
	cmpl	%eax, -8(%rbp)
	jl	.L8
	movl	$0, head(%rip)
	movl	$0, tail(%rip)
	movq	-32(%rbp), %rdx
	movl	-24(%rbp), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	jmp	.L9
.L15:
	movl	$0, %eax
	call	dequeue
	movq	%rax, p(%rip)
	movl	8+p(%rip), %eax
	andl	$0, %eax
	orl	%edx, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	%al, -36(%rbp)
	je	.L17
	movl	8+p(%rip), %eax
	addl	$1, %eax
	movl	%eax, 8+p(%rip)
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	h(%rip), %eax
	cmpl	%eax, %edx
	jge	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L12
	movl	p(%rip), %eax
	leal	1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L12
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	addl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L12:
	movl	p(%rip), %eax
	testl	%eax, %eax
	jle	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	leaq	(%rax,%rcx), %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L13
	movl	p(%rip), %eax
	leal	-1(%rax), %edx
	movl	4+p(%rip), %eax
	movslq	%eax, %rcx
	movslq	%edx, %rax
	imulq	$1000, %rax, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L13
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	next(%rip), %eax
	subl	$1, %eax
	movl	%eax, next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L13:
	movl	4+p(%rip), %eax
	leal	1(%rax), %edx
	movl	w(%rip), %eax
	cmpl	%eax, %edx
	jge	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L14
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	addl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L14
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	addl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L14:
	movl	4+p(%rip), %eax
	testl	%eax, %eax
	jle	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$88, %al
	je	.L9
	movl	p(%rip), %eax
	movl	4+p(%rip), %edx
	subl	$1, %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	(%rdx,%rax), %eax
	testl	%eax, %eax
	jne	.L9
	movq	p(%rip), %rax
	movq	%rax, next(%rip)
	movl	8+p(%rip), %eax
	movl	%eax, 8+next(%rip)
	movl	4+next(%rip), %eax
	subl	$1, %eax
	movl	%eax, 4+next(%rip)
	movq	next(%rip), %rdx
	movl	8+next(%rip), %eax
	movq	%rdx, %rdi
	movl	%eax, %esi
	call	enqueue
	movl	next(%rip), %eax
	movl	4+next(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1000, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	visited(%rip), %rax
	movl	$1, (%rdx,%rax)
.L9:
	movl	head(%rip), %edx
	movl	tail(%rip), %eax
	cmpl	%eax, %edx
	jne	.L15
	jmp	.L11
.L17:
	nop
.L11:
	movl	8+p(%rip), %eax
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE2:
	.size	bfs, .-bfs
	.section	.rodata
.LC0:
	.string	"%d %d %d"
.LC1:
	.string	"%s"
.LC2:
	.string	"%d\n"
	.text
	.globl	main
	.type	main, @function
main:
.LFB3:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	subq	$2048, %rsp
	movq	%fs:40, %rax
	movq	%rax, -8(%rbp)
	xorl	%eax, %eax
	leaq	n(%rip), %rax
	movq	%rax, %rcx
	leaq	w(%rip), %rax
	movq	%rax, %rdx
	leaq	h(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2040(%rbp)
	jmp	.L19
.L23:
	leaq	-2016(%rbp), %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	$0, -2036(%rbp)
	jmp	.L20
.L22:
	movl	-2036(%rbp), %eax
	cltq
	movzbl	-2016(%rbp,%rax), %eax
	movl	-2036(%rbp), %edx
	movslq	%edx, %rcx
	movl	-2040(%rbp), %edx
	movslq	%edx, %rdx
	imulq	$1000, %rdx, %rdx
	addq	%rdx, %rcx
	leaq	map(%rip), %rdx
	addq	%rcx, %rdx
	movb	%al, (%rdx)
	movl	-2036(%rbp), %eax
	movslq	%eax, %rdx
	movl	-2040(%rbp), %eax
	cltq
	imulq	$1000, %rax, %rax
	addq	%rax, %rdx
	leaq	map(%rip), %rax
	addq	%rdx, %rax
	movzbl	(%rax), %eax
	cmpb	$83, %al
	jne	.L21
	movl	-2040(%rbp), %eax
	movl	%eax, -2028(%rbp)
	movl	-2036(%rbp), %eax
	movl	%eax, -2024(%rbp)
.L21:
	addl	$1, -2036(%rbp)
.L20:
	movl	w(%rip), %eax
	cmpl	%eax, -2036(%rbp)
	jl	.L22
	addl	$1, -2040(%rbp)
.L19:
	movl	h(%rip), %eax
	cmpl	%eax, -2040(%rbp)
	jl	.L23
	movb	$1, -2041(%rbp)
	movl	$0, -2032(%rbp)
	jmp	.L24
.L25:
	movl	$0, -2020(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$48, %eax
	movsbl	%al, %edx
	movq	-2028(%rbp), %rcx
	movl	-2020(%rbp), %eax
	movq	%rcx, %rdi
	movl	%eax, %esi
	call	bfs
	addl	%eax, -2032(%rbp)
	movzbl	-2041(%rbp), %eax
	addl	$1, %eax
	movb	%al, -2041(%rbp)
	movq	p(%rip), %rax
	movq	%rax, -2028(%rbp)
	movl	8+p(%rip), %eax
	movl	%eax, -2020(%rbp)
.L24:
	movsbl	-2041(%rbp), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jle	.L25
	movl	-2032(%rbp), %eax
	movl	%eax, %esi
	leaq	.LC2(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	movl	$0, %eax
	movq	-8(%rbp), %rdx
	subq	%fs:40, %rdx
	je	.L27
	call	__stack_chk_fail@PLT
.L27:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE3:
	.size	main, .-main
	.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:
