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 <math.h>
#include <stdlib.h>

int i,j,k,n,m,l,x,y,build[1001][2],assign[1001],assign2[1001],prev[1001][1001];
double route[11][1001][1001];

void backtrack(int from,int to){
	int z=prev[from][to];

	if(from==to)return;
	if(z==from){
		printf("%d ",assign[from]);
		return;
	}
	backtrack(from,z);
	backtrack(z,to);
	
}

int main(){
	while(scanf("%d",&n)*n){
		for(i=0;i<n;i++){
			scanf("%d %d %d",&assign[i],&build[i][0],&build[i][1]);
			assign2[assign[i]]=i;
		}
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				l=(build[i][0]-build[j][0])*(build[i][0]-build[j][0])+(build[i][1]-build[j][1])*(build[i][1]-build[j][1]);
				if(l<=2500){
					route[0][i][j]=sqrt((double)l);
					route[0][j][i]=sqrt((double)l);
					prev[i][j]=i;
					prev[j][i]=j;
				}
				else{
					route[0][i][j]=999999999;
					route[0][j][i]=999999999;
				}
			}
		}

		for(l=1;pow(2.0,l)<n-1;l++){
			for(i=0;i<n;i++){
				for(j=0;j<n;j++){
					route[l][i][j]=route[l-1][i][j];
					for(k=0;k<n;k++){
						if(route[l][i][j]>route[l-1][i][k]+route[l-1][k][j]){
							route[l][i][j]=route[l-1][i][k]+route[l-1][k][j];
							prev[i][j]=k;
						}
					}
				}
			}
		}

		l--;

		for(scanf("%d",&m);m>0;m--){
			scanf("%d %d",&x,&y);
			x=assign2[x];
			y=assign2[y];
			if(x==y){
				printf("%d\n",assign[y]);
			}
			else if(route[l][x][y]<999999999){
				backtrack(x,y);
				printf("%d\n",assign[y]);
			}
			else printf("NA\n");
		}

	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	i
	.bss
	.align 4
	.type	i, @object
	.size	i, 4
i:
	.zero	4
	.globl	j
	.align 4
	.type	j, @object
	.size	j, 4
j:
	.zero	4
	.globl	k
	.align 4
	.type	k, @object
	.size	k, 4
k:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	l
	.align 4
	.type	l, @object
	.size	l, 4
l:
	.zero	4
	.globl	x
	.align 4
	.type	x, @object
	.size	x, 4
x:
	.zero	4
	.globl	y
	.align 4
	.type	y, @object
	.size	y, 4
y:
	.zero	4
	.globl	build
	.align 32
	.type	build, @object
	.size	build, 8008
build:
	.zero	8008
	.globl	assign
	.align 32
	.type	assign, @object
	.size	assign, 4004
assign:
	.zero	4004
	.globl	assign2
	.align 32
	.type	assign2, @object
	.size	assign2, 4004
assign2:
	.zero	4004
	.globl	prev
	.align 32
	.type	prev, @object
	.size	prev, 4008004
prev:
	.zero	4008004
	.globl	route
	.align 32
	.type	route, @object
	.size	route, 88176088
route:
	.zero	88176088
	.section	.rodata
.LC0:
	.string	"%d "
	.text
	.globl	backtrack
	.type	backtrack, @function
backtrack:
.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
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	movl	-24(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	prev(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	movl	-20(%rbp), %eax
	cmpl	-24(%rbp), %eax
	je	.L5
	movl	-4(%rbp), %eax
	cmpl	-20(%rbp), %eax
	jne	.L4
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L1
.L4:
	movl	-4(%rbp), %edx
	movl	-20(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	-24(%rbp), %edx
	movl	-4(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	jmp	.L1
.L5:
	nop
.L1:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	backtrack, .-backtrack
	.section	.rodata
.LC1:
	.string	"%d %d %d"
.LC4:
	.string	"%d"
.LC5:
	.string	"%d %d"
.LC6:
	.string	"%d\n"
.LC7:
	.string	"NA"
	.text
	.globl	main
	.type	main, @function
main:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	jmp	.L7
.L32:
	movl	$0, i(%rip)
	jmp	.L8
.L9:
	movl	i(%rip), %eax
	cltq
	salq	$3, %rax
	leaq	4(%rax), %rdx
	leaq	build(%rip), %rax
	leaq	(%rdx,%rax), %rcx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	addq	%rax, %rdx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rsi
	leaq	assign(%rip), %rax
	addq	%rsi, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	i(%rip), %eax
	movslq	%edx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	assign2(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L8:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L9
	movl	$0, i(%rip)
	jmp	.L10
.L15:
	movl	i(%rip), %eax
	movl	%eax, j(%rip)
	jmp	.L11
.L14:
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%esi, %edi
	imull	%eax, %edi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	imull	%esi, %eax
	addl	%edi, %eax
	movl	%eax, l(%rip)
	movl	l(%rip), %eax
	cmpl	$2500, %eax
	jg	.L12
	movl	l(%rip), %eax
	pxor	%xmm3, %xmm3
	cvtsi2sdl	%eax, %xmm3
	movq	%xmm3, %rax
	movl	i(%rip), %ebx
	movl	j(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	l(%rip), %eax
	pxor	%xmm4, %xmm4
	cvtsi2sdl	%eax, %xmm4
	movq	%xmm4, %rax
	movl	j(%rip), %ebx
	movl	i(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	i(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	j(%rip), %edx
	movl	i(%rip), %ecx
	movl	j(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	jmp	.L13
.L12:
	movl	i(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
	movl	j(%rip), %eax
	movl	i(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
.L13:
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L11:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L14
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L10:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L15
	movl	$1, l(%rip)
	jmp	.L16
.L25:
	movl	$0, i(%rip)
	jmp	.L17
.L24:
	movl	$0, j(%rip)
	jmp	.L18
.L23:
	movl	l(%rip), %eax
	leal	-1(%rax), %r8d
	movl	i(%rip), %esi
	movl	j(%rip), %edi
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%edi, %r9
	movslq	%r8d, %rdi
	movslq	%esi, %rsi
	imulq	$1002001, %rdi, %rdi
	imulq	$1001, %rsi, %rsi
	addq	%rdi, %rsi
	addq	%r9, %rsi
	leaq	0(,%rsi,8), %rdi
	leaq	route(%rip), %rsi
	movsd	(%rdi,%rsi), %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	$0, k(%rip)
	jmp	.L19
.L22:
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm2
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	addsd	%xmm2, %xmm1
	comisd	%xmm1, %xmm0
	jbe	.L20
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	addsd	%xmm1, %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	k(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
.L20:
	movl	k(%rip), %eax
	addl	$1, %eax
	movl	%eax, k(%rip)
.L19:
	movl	k(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L22
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L18:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L23
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L17:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L24
	movl	l(%rip), %eax
	addl	$1, %eax
	movl	%eax, l(%rip)
.L16:
	movl	l(%rip), %eax
	pxor	%xmm0, %xmm0
	cvtsi2sdl	%eax, %xmm0
	movq	.LC3(%rip), %rax
	movapd	%xmm0, %xmm1
	movq	%rax, %xmm0
	call	pow@PLT
	movl	n(%rip), %eax
	subl	$1, %eax
	pxor	%xmm1, %xmm1
	cvtsi2sdl	%eax, %xmm1
	comisd	%xmm0, %xmm1
	ja	.L25
	movl	l(%rip), %eax
	subl	$1, %eax
	movl	%eax, l(%rip)
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	jmp	.L26
.L31:
	leaq	y(%rip), %rax
	movq	%rax, %rdx
	leaq	x(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC5(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	x(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, x(%rip)
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, y(%rip)
	movl	x(%rip), %edx
	movl	y(%rip), %eax
	cmpl	%eax, %edx
	jne	.L27
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L27:
	movl	l(%rip), %edx
	movl	x(%rip), %eax
	movl	y(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movsd	.LC2(%rip), %xmm0
	comisd	%xmm1, %xmm0
	jbe	.L36
	movl	y(%rip), %edx
	movl	x(%rip), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L36:
	leaq	.LC7(%rip), %rax
	movq	%rax, %rdi
	call	puts@PLT
.L28:
	movl	m(%rip), %eax
	subl	$1, %eax
	movl	%eax, m(%rip)
.L26:
	movl	m(%rip), %eax
	testl	%eax, %eax
	jg	.L31
.L7:
	leaq	n(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	n(%rip), %edx
	imull	%edx, %eax
	testl	%eax, %eax
	jne	.L32
	movl	$0, %eax
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	main, .-main
	.section	.rodata
	.align 8
.LC2:
	.long	-8388608
	.long	1104006500
	.align 8
.LC3:
	.long	0
	.long	1073741824
	.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
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d "
	.text
	.p2align 4
	.globl	backtrack
	.type	backtrack, @function
backtrack:
.LFB39:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movslq	%edi, %rax
	movslq	%esi, %rdx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	leaq	assign(%rip), %r14
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	leaq	prev(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rax, %rbx
	subq	$104, %rsp
	.cfi_def_cfa_offset 160
	movq	%rax, (%rsp)
	imulq	$1001, %rax, %rax
	movl	%esi, 68(%rsp)
	movq	%rdx, 88(%rsp)
	addq	%rdx, %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 16(%rsp)
	cmpl	%ebx, %esi
	je	.L1
.L3:
	movl	16(%rsp), %eax
	cmpl	%ebx, %eax
	je	.L4
	movslq	%eax, %rsi
	imulq	$1001, (%rsp), %rax
	movl	%ebx, %ecx
	movq	%rsi, 72(%rsp)
	addq	%rsi, %rax
	movl	(%r12,%rax,4), %ebx
	movslq	%ebx, %rax
	movl	%ebx, 12(%rsp)
	cmpl	%eax, %ecx
	je	.L7
.L41:
	movslq	%ecx, %rbx
	movq	%rax, %rsi
	movq	%rax, (%rsp)
	imulq	$1001, %rbx, %rax
	movq	%rbx, %rbp
	addq	%rsi, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 36(%rsp)
	cmpl	%eax, %ecx
	je	.L10
.L40:
	movq	%rax, %rdi
	movq	%rax, 56(%rsp)
	imulq	$1001, %rbp, %rax
	movq	%rbp, %rbx
	addq	%rdi, %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 20(%rsp)
.L11:
	movslq	20(%rsp), %rax
	cmpl	%ecx, %eax
	je	.L13
	movq	%rax, %rsi
	movq	%rax, 80(%rsp)
	imulq	$1001, %rbx, %rax
	movq	%rbx, %rbp
	movl	%ecx, %ebx
	addq	%rsi, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 32(%rsp)
	cmpl	%eax, %ebx
	je	.L16
.L39:
	movq	%rax, %rcx
	movq	%rax, 40(%rsp)
	imulq	$1001, %rbp, %rax
	movq	%rbp, %r13
	movl	%ebx, %ebp
	leaq	.LC0(%rip), %r15
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 8(%rsp)
	cmpl	%eax, %ebp
	je	.L19
.L38:
	movq	%rax, %rcx
	movq	%rax, 24(%rsp)
	imulq	$1001, %r13, %rax
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rbx
.L20:
	cmpl	%ebp, %ebx
	je	.L22
	imulq	$1001, %r13, %rax
	movslq	%ebx, %rcx
	movslq	%ebp, %rdi
	movq	%rcx, 48(%rsp)
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rbp
	cmpl	%ebp, %edi
	je	.L36
.L25:
	movslq	%edi, %rax
	movslq	%ebp, %r13
	movl	%ebx, 64(%rsp)
	imulq	$1001, %rax, %rax
	addq	%r13, %rax
	movl	(%r12,%rax,4), %edx
	movl	%edx, %ebx
	cmpl	%ebx, %edi
	je	.L37
.L26:
	movl	%ebx, %esi
	call	backtrack
	movslq	%ebx, %rax
	movslq	%ebx, %rdi
	imulq	$1001, %rax, %rax
	addq	%r13, %rax
	movl	(%r12,%rax,4), %eax
	cmpl	%ebp, %edi
	je	.L33
	movl	%eax, %ebx
	cmpl	%ebx, %edi
	jne	.L26
.L37:
	movl	(%r14,%rdi,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	movl	64(%rsp), %ebx
	call	__printf_chk@PLT
.L27:
	imulq	$1001, %r13, %rax
	addq	48(%rsp), %rax
	movslq	%ebp, %rdi
	movl	(%r12,%rax,4), %eax
	cmpl	%ebp, %ebx
	je	.L24
	movslq	%eax, %rbp
	cmpl	%ebp, %edi
	jne	.L25
.L36:
	movl	(%r14,%rbp,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	movslq	%ebx, %r13
	call	__printf_chk@PLT
	movq	%r13, %rbp
.L24:
	imulq	$1001, %r13, %rax
	addq	24(%rsp), %rax
	movslq	(%r12,%rax,4), %rbx
	cmpl	8(%rsp), %ebp
	jne	.L20
.L21:
	movl	8(%rsp), %ebp
	movl	32(%rsp), %ecx
	imulq	$1001, 24(%rsp), %rax
	addq	40(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	cmpl	%ecx, %ebp
	je	.L18
	movl	%eax, 8(%rsp)
	movslq	%ebp, %r13
	cmpl	%eax, %ebp
	jne	.L38
.L19:
	movl	(%r14,%r13,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L18:
	imulq	$1001, 40(%rsp), %rax
	addq	80(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	32(%rsp), %ebx
	cmpl	%ebx, 20(%rsp)
	je	.L31
	movl	%eax, 32(%rsp)
	movslq	%ebx, %rbp
	cmpl	%eax, %ebx
	jne	.L39
.L16:
	movl	(%r14,%rbp,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	movl	20(%rsp), %ecx
.L15:
	movslq	%ecx, %rbx
	imulq	$1001, %rbx, %rax
	addq	56(%rsp), %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 20(%rsp)
	cmpl	36(%rsp), %ecx
	jne	.L11
.L12:
	imulq	$1001, 56(%rsp), %rax
	addq	(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	36(%rsp), %ecx
	cmpl	12(%rsp), %ecx
	je	.L9
	movl	%eax, 36(%rsp)
	movslq	%ecx, %rbp
	cmpl	%eax, %ecx
	jne	.L40
.L10:
	movl	(%r14,%rbp,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L9:
	movl	12(%rsp), %edx
	imulq	$1001, (%rsp), %rax
	addq	72(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	%edx, %ecx
	cmpl	%edx, 16(%rsp)
	je	.L30
	movl	%eax, 12(%rsp)
	cmpl	%eax, %ecx
	jne	.L41
.L7:
	cltq
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	movl	(%r14,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
	movslq	16(%rsp), %rax
	movq	%rax, (%rsp)
	movq	%rax, %rbx
	jmp	.L6
.L22:
	movl	(%r14,%rbx,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L21
	.p2align 4,,10
	.p2align 3
.L33:
	movl	64(%rsp), %ebx
	jmp	.L27
.L31:
	movl	%ebx, %ecx
	jmp	.L15
.L13:
	movslq	20(%rsp), %rax
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	movl	(%r14,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L12
.L30:
	movl	%edx, %ebx
.L6:
	imulq	$1001, (%rsp), %rax
	addq	88(%rsp), %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 16(%rsp)
	cmpl	%ebx, 68(%rsp)
	jne	.L3
.L1:
	addq	$104, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L4:
	.cfi_restore_state
	movslq	16(%rsp), %rax
	leaq	assign(%rip), %rdx
	movl	$1, %edi
	leaq	.LC0(%rip), %rsi
	movl	(%rdx,%rax,4), %edx
	addq	$104, %rsp
	.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
	jmp	__printf_chk@PLT
	.cfi_endproc
.LFE39:
	.size	backtrack, .-backtrack
	.section	.rodata.str1.1
.LC1:
	.string	"%d %d %d"
.LC5:
	.string	"%d"
.LC6:
	.string	"%d %d"
.LC7:
	.string	"%d\n"
.LC8:
	.string	"NA"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB40:
	.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	$88, %rsp
	.cfi_def_cfa_offset 144
.L43:
	leaq	n(%rip), %rsi
	leaq	.LC5(%rip), %rdi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movl	n(%rip), %ecx
	imull	%ecx, %eax
	testl	%eax, %eax
	je	.L92
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L44
	xorl	%eax, %eax
	leaq	build(%rip), %r8
	leaq	assign(%rip), %rbp
	leaq	.LC1(%rip), %r12
	leaq	assign2(%rip), %rbx
.L45:
	cltq
	movq	%r12, %rdi
	leaq	0(,%rax,8), %rdx
	leaq	0(%rbp,%rax,4), %rsi
	xorl	%eax, %eax
	leaq	4(%r8,%rdx), %rcx
	addq	%r8, %rdx
	call	__isoc99_scanf@PLT
	movslq	i(%rip), %rdx
	movl	n(%rip), %ecx
	leaq	build(%rip), %r8
	movq	%rdx, %rax
	movslq	0(%rbp,%rdx,4), %rdx
	movl	%eax, (%rbx,%rdx,4)
	addl	$1, %eax
	cmpl	%ecx, %eax
	movl	%eax, i(%rip)
	jl	.L45
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L44
	leaq	prev(%rip), %rax
	leaq	route(%rip), %rdi
	pxor	%xmm3, %xmm3
	xorl	%r11d, %r11d
	movq	%rax, 8(%rsp)
	movsd	.LC3(%rip), %xmm2
	movq	%rax, 24(%rsp)
	movq	%rdi, 16(%rsp)
	movslq	%ecx, %rdi
	movq	%rdi, 40(%rsp)
	leaq	4(%r8), %rdi
.L54:
	movq	16(%rsp), %r13
	movl	%r11d, 36(%rsp)
	movl	%r11d, %r10d
	movq	%r11, %rbx
	movl	(%r8,%r11,8), %r9d
	movl	(%rdi,%r11,8), %esi
	movl	%r11d, j(%rip)
	movq	24(%rsp), %r14
	movq	%r13, %r12
	jmp	.L46
.L49:
	movsd	%xmm2, (%r12)
	movsd	%xmm2, 0(%r13)
.L53:
	addl	$1, %ebp
	addq	$1, %rbx
	addq	$8, %r12
	addq	$8008, %r13
	movl	%ebp, j(%rip)
	addq	$4004, %r14
	cmpl	%ebx, %ecx
	jle	.L93
.L46:
	movl	%r9d, %eax
	movl	%esi, %edx
	subl	(%r8,%rbx,8), %eax
	subl	(%rdi,%rbx,8), %edx
	imull	%eax, %eax
	movl	%ebx, %ebp
	movl	%ebx, %r15d
	imull	%edx, %edx
	addl	%edx, %eax
	movl	%eax, l(%rip)
	cmpl	$2500, %eax
	jg	.L49
	pxor	%xmm1, %xmm1
	cvtsi2sdl	%eax, %xmm1
	ucomisd	%xmm1, %xmm3
	ja	.L88
	sqrtsd	%xmm1, %xmm1
	movsd	%xmm1, (%r12)
.L52:
	movq	8(%rsp), %rax
	movsd	%xmm1, 0(%r13)
	movl	%r10d, (%rax,%rbx,4)
	movl	%r15d, (%r14)
	jmp	.L53
.L93:
	movl	36(%rsp), %r13d
	addq	$1, %r11
	addq	$4004, 8(%rsp)
	addq	$8016, 16(%rsp)
	addq	$4008, 24(%rsp)
	addl	$1, %r13d
	movl	%r13d, i(%rip)
	cmpq	40(%rsp), %r11
	jne	.L54
	cmpl	%r13d, %ecx
	jle	.L44
.L47:
	movl	%r13d, %eax
	addl	$1, %r13d
	cmpl	%r13d, %ecx
	jg	.L47
	movl	%eax, j(%rip)
	movl	%r13d, i(%rip)
.L44:
	leal	-1(%rcx), %ebx
	leaq	4+prev(%rip), %rdx
	pxor	%xmm2, %xmm2
	xorl	%ebp, %ebp
	cvtsi2sdl	%ebx, %xmm2
	leaq	0(,%rbx,4), %rdi
	movl	$1, 8(%rsp)
	addq	%rdi, %rdx
	leaq	1(%rbx), %r14
	movq	%rdi, 24(%rsp)
	movq	%rdx, 16(%rsp)
	imulq	$-8008, %r14, %r14
.L55:
	movl	8(%rsp), %eax
	pxor	%xmm1, %xmm1
	movl	%ecx, 36(%rsp)
	movsd	%xmm2, 40(%rsp)
	cvtsi2sdl	%eax, %xmm1
	movl	%eax, l(%rip)
	movq	.LC4(%rip), %rax
	movq	%rax, %xmm0
	call	pow@PLT
	movsd	40(%rsp), %xmm2
	movl	36(%rsp), %ecx
	comisd	%xmm0, %xmm2
	jbe	.L94
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L56
	leaq	route(%rip), %rax
	movq	16(%rsp), %r10
	xorl	%r13d, %r13d
	movq	$-8016008, %r12
	movq	$-4, %r15
	leaq	0(%rbp,%rax), %r8
	subq	%rbp, %r12
	subq	24(%rsp), %r15
	.p2align 4,,10
	.p2align 3
.L61:
	leaq	8016008(%r8), %rdi
	leaq	(%r15,%r10), %r9
	leaq	-8016008(%r13), %r11
	.p2align 4,,10
	.p2align 3
.L60:
	leaq	(%r12,%rdi), %rax
	leaq	(%r11,%rdi), %rdx
	movsd	(%rax,%rbp), %xmm1
	xorl	%eax, %eax
	movsd	%xmm1, (%rdi)
	jmp	.L59
	.p2align 4,,10
	.p2align 3
.L73:
	movq	%rsi, %rax
.L59:
	movsd	(%r8,%rax,8), %xmm0
	addsd	(%rdx), %xmm0
	comisd	%xmm0, %xmm1
	jbe	.L57
	movl	%eax, (%r9)
	movapd	%xmm0, %xmm1
	movsd	%xmm0, (%rdi)
.L57:
	leaq	1(%rax), %rsi
	addq	$8008, %rdx
	cmpq	%rbx, %rax
	jne	.L73
	addq	$4, %r9
	addq	$8, %rdi
	cmpq	%r10, %r9
	jne	.L60
	subq	$8008, %r13
	leaq	4004(%r9), %r10
	addq	$8008, %r8
	cmpq	%r14, %r13
	jne	.L61
	movl	%ecx, k(%rip)
	movl	%ecx, j(%rip)
	movl	%ecx, i(%rip)
.L56:
	addl	$1, 8(%rsp)
	addq	$8016008, %rbp
	jmp	.L55
.L94:
	movl	8(%rsp), %eax
	leaq	m(%rip), %rsi
	leaq	.LC5(%rip), %rdi
	leaq	assign2(%rip), %rbx
	leaq	y(%rip), %r15
	subl	$1, %eax
	leaq	prev(%rip), %rbp
	movl	%eax, l(%rip)
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movl	m(%rip), %eax
	testl	%eax, %eax
	jle	.L43
.L63:
	leaq	.LC6(%rip), %rdi
	movq	%r15, %rdx
	leaq	x(%rip), %rsi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movslq	x(%rip), %rax
	movslq	(%rbx,%rax,4), %rdi
	movslq	y(%rip), %rax
	movl	(%rbx,%rax,4), %r13d
	movl	%edi, x(%rip)
	movl	%r13d, y(%rip)
	cmpl	%r13d, %edi
	je	.L95
	movslq	l(%rip), %rdx
	movslq	%edi, %rax
	movslq	%r13d, %r14
	leaq	route(%rip), %rcx
	imulq	$1001, %rax, %rax
	movsd	.LC3(%rip), %xmm4
	imulq	$1002001, %rdx, %rdx
	addq	%rax, %rdx
	addq	%r14, %rdx
	comisd	(%rcx,%rdx,8), %xmm4
	jbe	.L89
	addq	%r14, %rax
	movl	0(%rbp,%rax,4), %r12d
	cmpl	%r12d, %edi
	je	.L96
.L68:
	movl	%r12d, %esi
	call	backtrack
	movslq	%r12d, %rax
	movslq	%r12d, %rdi
	imulq	$1001, %rax, %rax
	addq	%r14, %rax
	movl	0(%rbp,%rax,4), %eax
	cmpl	%edi, %r13d
	je	.L97
	movl	%eax, %r12d
	cmpl	%r12d, %edi
	jne	.L68
.L96:
	leaq	assign(%rip), %r12
	leaq	.LC0(%rip), %rsi
	xorl	%eax, %eax
	movl	(%r12,%rdi,4), %edx
	movl	$1, %edi
	call	__printf_chk@PLT
.L69:
	movslq	y(%rip), %rax
	leaq	.LC7(%rip), %rsi
	movl	$1, %edi
	movl	(%r12,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L65:
	movl	m(%rip), %eax
	subl	$1, %eax
	movl	%eax, m(%rip)
	testl	%eax, %eax
	jg	.L63
	jmp	.L43
.L89:
	leaq	.LC8(%rip), %rdi
	call	puts@PLT
	jmp	.L65
.L95:
	leaq	assign(%rip), %r12
	leaq	.LC7(%rip), %rsi
	xorl	%eax, %eax
	movl	(%r12,%rdi,4), %edx
	movl	$1, %edi
	call	__printf_chk@PLT
	jmp	.L65
.L97:
	leaq	assign(%rip), %r12
	jmp	.L69
.L92:
	addq	$88, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L88:
	.cfi_restore_state
	movapd	%xmm1, %xmm0
	movq	%r11, 72(%rsp)
	movl	%esi, 68(%rsp)
	movl	%r9d, 64(%rsp)
	movl	%r10d, 60(%rsp)
	movl	%ecx, 56(%rsp)
	movsd	%xmm1, 48(%rsp)
	call	sqrt@PLT
	movsd	48(%rsp), %xmm1
	movsd	%xmm0, (%r12)
	movapd	%xmm1, %xmm0
	call	sqrt@PLT
	movq	.LC3(%rip), %rax
	leaq	build(%rip), %r8
	movq	72(%rsp), %r11
	movl	68(%rsp), %esi
	movl	56(%rsp), %ecx
	movapd	%xmm0, %xmm1
	pxor	%xmm3, %xmm3
	movl	64(%rsp), %r9d
	movl	60(%rsp), %r10d
	movq	%rax, %xmm2
	leaq	4(%r8), %rdi
	jmp	.L52
	.cfi_endproc
.LFE40:
	.size	main, .-main
	.globl	route
	.bss
	.align 32
	.type	route, @object
	.size	route, 88176088
route:
	.zero	88176088
	.globl	prev
	.align 32
	.type	prev, @object
	.size	prev, 4008004
prev:
	.zero	4008004
	.globl	assign2
	.align 32
	.type	assign2, @object
	.size	assign2, 4004
assign2:
	.zero	4004
	.globl	assign
	.align 32
	.type	assign, @object
	.size	assign, 4004
assign:
	.zero	4004
	.globl	build
	.align 32
	.type	build, @object
	.size	build, 8008
build:
	.zero	8008
	.globl	y
	.align 4
	.type	y, @object
	.size	y, 4
y:
	.zero	4
	.globl	x
	.align 4
	.type	x, @object
	.size	x, 4
x:
	.zero	4
	.globl	l
	.align 4
	.type	l, @object
	.size	l, 4
l:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	k
	.align 4
	.type	k, @object
	.size	k, 4
k:
	.zero	4
	.globl	j
	.align 4
	.type	j, @object
	.size	j, 4
j:
	.zero	4
	.globl	i
	.align 4
	.type	i, @object
	.size	i, 4
i:
	.zero	4
	.section	.rodata.cst8,"aM",@progbits,8
	.align 8
.LC3:
	.long	-8388608
	.long	1104006500
	.align 8
.LC4:
	.long	0
	.long	1073741824
	.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
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"%d "
	.text
	.p2align 4
	.globl	backtrack
	.type	backtrack, @function
backtrack:
.LFB39:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movslq	%edi, %rax
	movslq	%esi, %rdx
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	leaq	assign(%rip), %r14
	pushq	%r13
	.cfi_def_cfa_offset 32
	.cfi_offset 13, -32
	pushq	%r12
	.cfi_def_cfa_offset 40
	.cfi_offset 12, -40
	leaq	prev(%rip), %r12
	pushq	%rbp
	.cfi_def_cfa_offset 48
	.cfi_offset 6, -48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	movq	%rax, %rbx
	subq	$104, %rsp
	.cfi_def_cfa_offset 160
	movq	%rax, (%rsp)
	imulq	$1001, %rax, %rax
	movl	%esi, 68(%rsp)
	movq	%rdx, 88(%rsp)
	addq	%rdx, %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 16(%rsp)
	cmpl	%ebx, %esi
	je	.L1
.L3:
	movl	16(%rsp), %eax
	cmpl	%ebx, %eax
	je	.L4
	movslq	%eax, %rsi
	imulq	$1001, (%rsp), %rax
	movl	%ebx, %ecx
	movq	%rsi, 72(%rsp)
	addq	%rsi, %rax
	movl	(%r12,%rax,4), %ebx
	movslq	%ebx, %rax
	movl	%ebx, 12(%rsp)
	cmpl	%eax, %ecx
	je	.L7
.L41:
	movslq	%ecx, %rbx
	movq	%rax, %rsi
	movq	%rax, (%rsp)
	imulq	$1001, %rbx, %rax
	movq	%rbx, %rbp
	addq	%rsi, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 36(%rsp)
	cmpl	%eax, %ecx
	je	.L10
.L40:
	movq	%rax, %rdi
	movq	%rax, 56(%rsp)
	imulq	$1001, %rbp, %rax
	movq	%rbp, %rbx
	addq	%rdi, %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 20(%rsp)
.L11:
	movslq	20(%rsp), %rax
	cmpl	%ecx, %eax
	je	.L13
	movq	%rax, %rsi
	movq	%rax, 80(%rsp)
	imulq	$1001, %rbx, %rax
	movq	%rbx, %rbp
	movl	%ecx, %ebx
	addq	%rsi, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 32(%rsp)
	cmpl	%eax, %ebx
	je	.L16
.L39:
	movq	%rax, %rcx
	movq	%rax, 40(%rsp)
	imulq	$1001, %rbp, %rax
	movq	%rbp, %r13
	movl	%ebx, %ebp
	leaq	.LC0(%rip), %r15
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rax
	movl	%eax, 8(%rsp)
	cmpl	%eax, %ebp
	je	.L19
.L38:
	movq	%rax, %rcx
	movq	%rax, 24(%rsp)
	imulq	$1001, %r13, %rax
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rbx
.L20:
	cmpl	%ebp, %ebx
	je	.L22
	imulq	$1001, %r13, %rax
	movslq	%ebx, %rcx
	movslq	%ebp, %rdi
	movq	%rcx, 48(%rsp)
	addq	%rcx, %rax
	movslq	(%r12,%rax,4), %rbp
	cmpl	%ebp, %edi
	je	.L36
.L25:
	movslq	%edi, %rax
	movslq	%ebp, %r13
	movl	%ebx, 64(%rsp)
	imulq	$1001, %rax, %rax
	addq	%r13, %rax
	movl	(%r12,%rax,4), %edx
	movl	%edx, %ebx
	cmpl	%ebx, %edi
	je	.L37
.L26:
	movl	%ebx, %esi
	call	backtrack
	movslq	%ebx, %rax
	movslq	%ebx, %rdi
	imulq	$1001, %rax, %rax
	addq	%r13, %rax
	movl	(%r12,%rax,4), %eax
	cmpl	%ebp, %edi
	je	.L33
	movl	%eax, %ebx
	cmpl	%ebx, %edi
	jne	.L26
.L37:
	movl	(%r14,%rdi,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	movl	64(%rsp), %ebx
	call	__printf_chk@PLT
.L27:
	imulq	$1001, %r13, %rax
	addq	48(%rsp), %rax
	movslq	%ebp, %rdi
	movl	(%r12,%rax,4), %eax
	cmpl	%ebp, %ebx
	je	.L24
	movslq	%eax, %rbp
	cmpl	%ebp, %edi
	jne	.L25
.L36:
	movl	(%r14,%rbp,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	movslq	%ebx, %r13
	call	__printf_chk@PLT
	movq	%r13, %rbp
.L24:
	imulq	$1001, %r13, %rax
	addq	24(%rsp), %rax
	movslq	(%r12,%rax,4), %rbx
	cmpl	8(%rsp), %ebp
	jne	.L20
.L21:
	movl	8(%rsp), %ebp
	movl	32(%rsp), %ecx
	imulq	$1001, 24(%rsp), %rax
	addq	40(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	cmpl	%ecx, %ebp
	je	.L18
	movl	%eax, 8(%rsp)
	movslq	%ebp, %r13
	cmpl	%eax, %ebp
	jne	.L38
.L19:
	movl	(%r14,%r13,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L18:
	imulq	$1001, 40(%rsp), %rax
	addq	80(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	32(%rsp), %ebx
	cmpl	%ebx, 20(%rsp)
	je	.L31
	movl	%eax, 32(%rsp)
	movslq	%ebx, %rbp
	cmpl	%eax, %ebx
	jne	.L39
.L16:
	movl	(%r14,%rbp,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	movl	20(%rsp), %ecx
.L15:
	movslq	%ecx, %rbx
	imulq	$1001, %rbx, %rax
	addq	56(%rsp), %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 20(%rsp)
	cmpl	36(%rsp), %ecx
	jne	.L11
.L12:
	imulq	$1001, 56(%rsp), %rax
	addq	(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	36(%rsp), %ecx
	cmpl	12(%rsp), %ecx
	je	.L9
	movl	%eax, 36(%rsp)
	movslq	%ecx, %rbp
	cmpl	%eax, %ecx
	jne	.L40
.L10:
	movl	(%r14,%rbp,4), %edx
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L9:
	movl	12(%rsp), %edx
	imulq	$1001, (%rsp), %rax
	addq	72(%rsp), %rax
	movslq	(%r12,%rax,4), %rax
	movl	%edx, %ecx
	cmpl	%edx, 16(%rsp)
	je	.L30
	movl	%eax, 12(%rsp)
	cmpl	%eax, %ecx
	jne	.L41
.L7:
	cltq
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	movl	(%r14,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
	movslq	16(%rsp), %rax
	movq	%rax, (%rsp)
	movq	%rax, %rbx
	jmp	.L6
.L22:
	movl	(%r14,%rbx,4), %edx
	movq	%r15, %rsi
	movl	$1, %edi
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L21
	.p2align 4,,10
	.p2align 3
.L33:
	movl	64(%rsp), %ebx
	jmp	.L27
.L31:
	movl	%ebx, %ecx
	jmp	.L15
.L13:
	movslq	20(%rsp), %rax
	leaq	.LC0(%rip), %rsi
	movl	$1, %edi
	movl	(%r14,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
	jmp	.L12
.L30:
	movl	%edx, %ebx
.L6:
	imulq	$1001, (%rsp), %rax
	addq	88(%rsp), %rax
	movl	(%r12,%rax,4), %eax
	movl	%eax, 16(%rsp)
	cmpl	%ebx, 68(%rsp)
	jne	.L3
.L1:
	addq	$104, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L4:
	.cfi_restore_state
	movslq	16(%rsp), %rax
	leaq	assign(%rip), %rdx
	movl	$1, %edi
	leaq	.LC0(%rip), %rsi
	movl	(%rdx,%rax,4), %edx
	addq	$104, %rsp
	.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
	jmp	__printf_chk@PLT
	.cfi_endproc
.LFE39:
	.size	backtrack, .-backtrack
	.section	.rodata.str1.1
.LC1:
	.string	"%d %d %d"
.LC5:
	.string	"%d"
.LC6:
	.string	"%d %d"
.LC7:
	.string	"%d\n"
.LC8:
	.string	"NA"
	.section	.text.startup,"ax",@progbits
	.p2align 4
	.globl	main
	.type	main, @function
main:
.LFB40:
	.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	$88, %rsp
	.cfi_def_cfa_offset 144
.L43:
	leaq	n(%rip), %rsi
	leaq	.LC5(%rip), %rdi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movl	n(%rip), %ecx
	imull	%ecx, %eax
	testl	%eax, %eax
	je	.L92
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L44
	xorl	%eax, %eax
	leaq	build(%rip), %r8
	leaq	assign(%rip), %rbp
	leaq	.LC1(%rip), %r12
	leaq	assign2(%rip), %rbx
.L45:
	cltq
	movq	%r12, %rdi
	leaq	0(,%rax,8), %rdx
	leaq	0(%rbp,%rax,4), %rsi
	xorl	%eax, %eax
	leaq	4(%r8,%rdx), %rcx
	addq	%r8, %rdx
	call	__isoc99_scanf@PLT
	movslq	i(%rip), %rdx
	movl	n(%rip), %ecx
	leaq	build(%rip), %r8
	movq	%rdx, %rax
	movslq	0(%rbp,%rdx,4), %rdx
	movl	%eax, (%rbx,%rdx,4)
	addl	$1, %eax
	cmpl	%ecx, %eax
	movl	%eax, i(%rip)
	jl	.L45
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L44
	leaq	prev(%rip), %rax
	leaq	route(%rip), %rdi
	pxor	%xmm3, %xmm3
	xorl	%r11d, %r11d
	movq	%rax, 8(%rsp)
	movsd	.LC3(%rip), %xmm2
	movq	%rax, 24(%rsp)
	movq	%rdi, 16(%rsp)
	movslq	%ecx, %rdi
	movq	%rdi, 40(%rsp)
	leaq	4(%r8), %rdi
.L54:
	movq	16(%rsp), %r13
	movl	%r11d, 36(%rsp)
	movl	%r11d, %r10d
	movq	%r11, %rbx
	movl	(%r8,%r11,8), %r9d
	movl	(%rdi,%r11,8), %esi
	movl	%r11d, j(%rip)
	movq	24(%rsp), %r14
	movq	%r13, %r12
	jmp	.L46
.L49:
	movsd	%xmm2, (%r12)
	movsd	%xmm2, 0(%r13)
.L53:
	addl	$1, %ebp
	addq	$1, %rbx
	addq	$8, %r12
	addq	$8008, %r13
	movl	%ebp, j(%rip)
	addq	$4004, %r14
	cmpl	%ebx, %ecx
	jle	.L93
.L46:
	movl	%r9d, %eax
	movl	%esi, %edx
	subl	(%r8,%rbx,8), %eax
	subl	(%rdi,%rbx,8), %edx
	imull	%eax, %eax
	movl	%ebx, %ebp
	movl	%ebx, %r15d
	imull	%edx, %edx
	addl	%edx, %eax
	movl	%eax, l(%rip)
	cmpl	$2500, %eax
	jg	.L49
	pxor	%xmm1, %xmm1
	cvtsi2sdl	%eax, %xmm1
	ucomisd	%xmm1, %xmm3
	ja	.L88
	sqrtsd	%xmm1, %xmm1
	movsd	%xmm1, (%r12)
.L52:
	movq	8(%rsp), %rax
	movsd	%xmm1, 0(%r13)
	movl	%r10d, (%rax,%rbx,4)
	movl	%r15d, (%r14)
	jmp	.L53
.L93:
	movl	36(%rsp), %r13d
	addq	$1, %r11
	addq	$4004, 8(%rsp)
	addq	$8016, 16(%rsp)
	addq	$4008, 24(%rsp)
	addl	$1, %r13d
	movl	%r13d, i(%rip)
	cmpq	40(%rsp), %r11
	jne	.L54
	cmpl	%r13d, %ecx
	jle	.L44
.L47:
	movl	%r13d, %eax
	addl	$1, %r13d
	cmpl	%r13d, %ecx
	jg	.L47
	movl	%eax, j(%rip)
	movl	%r13d, i(%rip)
.L44:
	leal	-1(%rcx), %ebx
	leaq	4+prev(%rip), %rdx
	pxor	%xmm2, %xmm2
	xorl	%ebp, %ebp
	cvtsi2sdl	%ebx, %xmm2
	leaq	0(,%rbx,4), %rdi
	movl	$1, 8(%rsp)
	addq	%rdi, %rdx
	leaq	1(%rbx), %r14
	movq	%rdi, 24(%rsp)
	movq	%rdx, 16(%rsp)
	imulq	$-8008, %r14, %r14
.L55:
	movl	8(%rsp), %eax
	pxor	%xmm1, %xmm1
	movl	%ecx, 36(%rsp)
	movsd	%xmm2, 40(%rsp)
	cvtsi2sdl	%eax, %xmm1
	movl	%eax, l(%rip)
	movq	.LC4(%rip), %rax
	movq	%rax, %xmm0
	call	pow@PLT
	movsd	40(%rsp), %xmm2
	movl	36(%rsp), %ecx
	comisd	%xmm0, %xmm2
	jbe	.L94
	movl	$0, i(%rip)
	testl	%ecx, %ecx
	jle	.L56
	leaq	route(%rip), %rax
	movq	16(%rsp), %r10
	xorl	%r13d, %r13d
	movq	$-8016008, %r12
	movq	$-4, %r15
	leaq	0(%rbp,%rax), %r8
	subq	%rbp, %r12
	subq	24(%rsp), %r15
	.p2align 4,,10
	.p2align 3
.L61:
	leaq	8016008(%r8), %rdi
	leaq	(%r15,%r10), %r9
	leaq	-8016008(%r13), %r11
	.p2align 4,,10
	.p2align 3
.L60:
	leaq	(%r12,%rdi), %rax
	leaq	(%r11,%rdi), %rdx
	movsd	(%rax,%rbp), %xmm1
	xorl	%eax, %eax
	movsd	%xmm1, (%rdi)
	jmp	.L59
	.p2align 4,,10
	.p2align 3
.L73:
	movq	%rsi, %rax
.L59:
	movsd	(%r8,%rax,8), %xmm0
	addsd	(%rdx), %xmm0
	comisd	%xmm0, %xmm1
	jbe	.L57
	movl	%eax, (%r9)
	movapd	%xmm0, %xmm1
	movsd	%xmm0, (%rdi)
.L57:
	leaq	1(%rax), %rsi
	addq	$8008, %rdx
	cmpq	%rbx, %rax
	jne	.L73
	addq	$4, %r9
	addq	$8, %rdi
	cmpq	%r10, %r9
	jne	.L60
	subq	$8008, %r13
	leaq	4004(%r9), %r10
	addq	$8008, %r8
	cmpq	%r14, %r13
	jne	.L61
	movl	%ecx, k(%rip)
	movl	%ecx, j(%rip)
	movl	%ecx, i(%rip)
.L56:
	addl	$1, 8(%rsp)
	addq	$8016008, %rbp
	jmp	.L55
.L94:
	movl	8(%rsp), %eax
	leaq	m(%rip), %rsi
	leaq	.LC5(%rip), %rdi
	leaq	assign2(%rip), %rbx
	leaq	y(%rip), %r15
	subl	$1, %eax
	leaq	prev(%rip), %rbp
	movl	%eax, l(%rip)
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movl	m(%rip), %eax
	testl	%eax, %eax
	jle	.L43
.L63:
	leaq	.LC6(%rip), %rdi
	movq	%r15, %rdx
	leaq	x(%rip), %rsi
	xorl	%eax, %eax
	call	__isoc99_scanf@PLT
	movslq	x(%rip), %rax
	movslq	(%rbx,%rax,4), %rdi
	movslq	y(%rip), %rax
	movl	(%rbx,%rax,4), %r13d
	movl	%edi, x(%rip)
	movl	%r13d, y(%rip)
	cmpl	%r13d, %edi
	je	.L95
	movslq	l(%rip), %rdx
	movslq	%edi, %rax
	movslq	%r13d, %r14
	leaq	route(%rip), %rcx
	imulq	$1001, %rax, %rax
	movsd	.LC3(%rip), %xmm4
	imulq	$1002001, %rdx, %rdx
	addq	%rax, %rdx
	addq	%r14, %rdx
	comisd	(%rcx,%rdx,8), %xmm4
	jbe	.L89
	addq	%r14, %rax
	movl	0(%rbp,%rax,4), %r12d
	cmpl	%r12d, %edi
	je	.L96
.L68:
	movl	%r12d, %esi
	call	backtrack
	movslq	%r12d, %rax
	movslq	%r12d, %rdi
	imulq	$1001, %rax, %rax
	addq	%r14, %rax
	movl	0(%rbp,%rax,4), %eax
	cmpl	%edi, %r13d
	je	.L97
	movl	%eax, %r12d
	cmpl	%r12d, %edi
	jne	.L68
.L96:
	leaq	assign(%rip), %r12
	leaq	.LC0(%rip), %rsi
	xorl	%eax, %eax
	movl	(%r12,%rdi,4), %edx
	movl	$1, %edi
	call	__printf_chk@PLT
.L69:
	movslq	y(%rip), %rax
	leaq	.LC7(%rip), %rsi
	movl	$1, %edi
	movl	(%r12,%rax,4), %edx
	xorl	%eax, %eax
	call	__printf_chk@PLT
.L65:
	movl	m(%rip), %eax
	subl	$1, %eax
	movl	%eax, m(%rip)
	testl	%eax, %eax
	jg	.L63
	jmp	.L43
.L89:
	leaq	.LC8(%rip), %rdi
	call	puts@PLT
	jmp	.L65
.L95:
	leaq	assign(%rip), %r12
	leaq	.LC7(%rip), %rsi
	xorl	%eax, %eax
	movl	(%r12,%rdi,4), %edx
	movl	$1, %edi
	call	__printf_chk@PLT
	jmp	.L65
.L97:
	leaq	assign(%rip), %r12
	jmp	.L69
.L92:
	addq	$88, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 56
	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
.L88:
	.cfi_restore_state
	movapd	%xmm1, %xmm0
	movq	%r11, 72(%rsp)
	movl	%esi, 68(%rsp)
	movl	%r9d, 64(%rsp)
	movl	%r10d, 60(%rsp)
	movl	%ecx, 56(%rsp)
	movsd	%xmm1, 48(%rsp)
	call	sqrt@PLT
	movsd	48(%rsp), %xmm1
	movsd	%xmm0, (%r12)
	movapd	%xmm1, %xmm0
	call	sqrt@PLT
	movq	.LC3(%rip), %rax
	leaq	build(%rip), %r8
	movq	72(%rsp), %r11
	movl	68(%rsp), %esi
	movl	56(%rsp), %ecx
	movapd	%xmm0, %xmm1
	pxor	%xmm3, %xmm3
	movl	64(%rsp), %r9d
	movl	60(%rsp), %r10d
	movq	%rax, %xmm2
	leaq	4(%r8), %rdi
	jmp	.L52
	.cfi_endproc
.LFE40:
	.size	main, .-main
	.globl	route
	.bss
	.align 32
	.type	route, @object
	.size	route, 88176088
route:
	.zero	88176088
	.globl	prev
	.align 32
	.type	prev, @object
	.size	prev, 4008004
prev:
	.zero	4008004
	.globl	assign2
	.align 32
	.type	assign2, @object
	.size	assign2, 4004
assign2:
	.zero	4004
	.globl	assign
	.align 32
	.type	assign, @object
	.size	assign, 4004
assign:
	.zero	4004
	.globl	build
	.align 32
	.type	build, @object
	.size	build, 8008
build:
	.zero	8008
	.globl	y
	.align 4
	.type	y, @object
	.size	y, 4
y:
	.zero	4
	.globl	x
	.align 4
	.type	x, @object
	.size	x, 4
x:
	.zero	4
	.globl	l
	.align 4
	.type	l, @object
	.size	l, 4
l:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	k
	.align 4
	.type	k, @object
	.size	k, 4
k:
	.zero	4
	.globl	j
	.align 4
	.type	j, @object
	.size	j, 4
j:
	.zero	4
	.globl	i
	.align 4
	.type	i, @object
	.size	i, 4
i:
	.zero	4
	.section	.rodata.cst8,"aM",@progbits,8
	.align 8
.LC3:
	.long	-8388608
	.long	1104006500
	.align 8
.LC4:
	.long	0
	.long	1073741824
	.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 <math.h>
#include <stdlib.h>

int i,j,k,n,m,l,x,y,build[1001][2],assign[1001],assign2[1001],prev[1001][1001];
double route[11][1001][1001];

void backtrack(int from,int to){
	int z=prev[from][to];

	if(from==to)return;
	if(z==from){
		printf("%d ",assign[from]);
		return;
	}
	backtrack(from,z);
	backtrack(z,to);
	
}

int main(){
	while(scanf("%d",&n)*n){
		for(i=0;i<n;i++){
			scanf("%d %d %d",&assign[i],&build[i][0],&build[i][1]);
			assign2[assign[i]]=i;
		}
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				l=(build[i][0]-build[j][0])*(build[i][0]-build[j][0])+(build[i][1]-build[j][1])*(build[i][1]-build[j][1]);
				if(l<=2500){
					route[0][i][j]=sqrt((double)l);
					route[0][j][i]=sqrt((double)l);
					prev[i][j]=i;
					prev[j][i]=j;
				}
				else{
					route[0][i][j]=999999999;
					route[0][j][i]=999999999;
				}
			}
		}

		for(l=1;pow(2.0,l)<n-1;l++){
			for(i=0;i<n;i++){
				for(j=0;j<n;j++){
					route[l][i][j]=route[l-1][i][j];
					for(k=0;k<n;k++){
						if(route[l][i][j]>route[l-1][i][k]+route[l-1][k][j]){
							route[l][i][j]=route[l-1][i][k]+route[l-1][k][j];
							prev[i][j]=k;
						}
					}
				}
			}
		}

		l--;

		for(scanf("%d",&m);m>0;m--){
			scanf("%d %d",&x,&y);
			x=assign2[x];
			y=assign2[y];
			if(x==y){
				printf("%d\n",assign[y]);
			}
			else if(route[l][x][y]<999999999){
				backtrack(x,y);
				printf("%d\n",assign[y]);
			}
			else printf("NA\n");
		}

	}
	return 0;
}
4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 2
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 36 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 36 117
16 190 90
17 49 100
18 100 70
19 130 100
20 71 69
21 200 110
22 5 150
1
1 22
0
 4
1 -1 0
2 30 0
3 71 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 5
20 144 131
13 130 32
14 80 140
15 36 117
16 190 90
17 49 100
18 100 70
19 130 100
20 71 69
21 200 110
22 5 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 2
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 69
21 200 110
22 140 150
1
1 22
0
 4
1 -2 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 36 117
16 190 90
17 60 100
18 100 70
19 130 100
20 71 19
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 202
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 109 100
18 110 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 58 40
4 0 60
2
1 3
1 2
22
1 0 0
2 150 40
3 30 20
4 180 150
5 40 80
6 130 130
7 72 28
8 172 118
9 50 50
10 160 82
11 90 105
12 144 131
13 197 6
14 80 140
15 36 117
16 190 90
17 60 100
18 100 138
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 2
4 180 150
5 40 80
6 130 130
7 72 28
8 172 202
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 109 100
18 110 70
19 130 100
20 71 69
21 200 110
22 120 150
1
1 22
0
 4
1 -1 0
2 30 0
3 60 40
4 0 60
2
1 3
1 4
22
1 0 0
2 150 40
3 30 2
4 180 150
5 40 80
6 130 130
7 72 28
8 172 202
9 50 50
10 160 82
11 90 105
12 144 131
13 130 64
14 80 140
15 38 117
16 190 90
17 109 100
18 110 70
19 130 100
20 31 69
21 200 110
22 120 150
1
1 22
0

1 2 3
NA
1 3 9 20 11 6 22
 1 2 3
1 2
1 3 9 20 11 6 22
 1 2 3
NA
1 3 9 5 15 22
 NA
NA
1 3 9 5 15 22
 1 2
NA
1 3 9 20 11 6 22
 1 2 3
NA
1 3 9 5 17 14 22
 1 2 3
NA
1 3 9 20 17 6 22
 1 2 3
1 2
1 3 9 20 11 18 22
 1 2 3
NA
1 3 7 20 17 6 22
 1 2 3
NA
1 3 7 9 5 15 14 22

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 <math.h>
#include <stdlib.h>

int i,j,k,n,m,l,x,y,build[1001][2],assign[1001],assign2[1001],prev[1001][1001];
double route[11][1001][1001];

void backtrack(int from,int to){
	int z=prev[from][to];

	if(from==to)return;
	if(z==from){
		printf("%d ",assign[from]);
		return;
	}
	backtrack(from,z);
	backtrack(z,to);
	
}

int main(){
	while(scanf("%d",&n)*n){
		for(i=0;i<n;i++){
			scanf("%d %d %d",&assign[i],&build[i][0],&build[i][1]);
			assign2[assign[i]]=i;
		}
		for(i=0;i<n;i++){
			for(j=i;j<n;j++){
				l=(build[i][0]-build[j][0])*(build[i][0]-build[j][0])+(build[i][1]-build[j][1])*(build[i][1]-build[j][1]);
				if(l<=2500){
					route[0][i][j]=sqrt((double)l);
					route[0][j][i]=sqrt((double)l);
					prev[i][j]=i;
					prev[j][i]=j;
				}
				else{
					route[0][i][j]=999999999;
					route[0][j][i]=999999999;
				}
			}
		}

		for(l=1;pow(2.0,l)<n-1;l++){
			for(i=0;i<n;i++){
				for(j=0;j<n;j++){
					route[l][i][j]=route[l-1][i][j];
					for(k=0;k<n;k++){
						if(route[l][i][j]>route[l-1][i][k]+route[l-1][k][j]){
							route[l][i][j]=route[l-1][i][k]+route[l-1][k][j];
							prev[i][j]=k;
						}
					}
				}
			}
		}

		l--;

		for(scanf("%d",&m);m>0;m--){
			scanf("%d %d",&x,&y);
			x=assign2[x];
			y=assign2[y];
			if(x==y){
				printf("%d\n",assign[y]);
			}
			else if(route[l][x][y]<999999999){
				backtrack(x,y);
				printf("%d\n",assign[y]);
			}
			else printf("NA\n");
		}

	}
	return 0;
}```

Unoptimized Assembly Code:

```assembly
	.file	"temp.c"
	.text
	.globl	i
	.bss
	.align 4
	.type	i, @object
	.size	i, 4
i:
	.zero	4
	.globl	j
	.align 4
	.type	j, @object
	.size	j, 4
j:
	.zero	4
	.globl	k
	.align 4
	.type	k, @object
	.size	k, 4
k:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	l
	.align 4
	.type	l, @object
	.size	l, 4
l:
	.zero	4
	.globl	x
	.align 4
	.type	x, @object
	.size	x, 4
x:
	.zero	4
	.globl	y
	.align 4
	.type	y, @object
	.size	y, 4
y:
	.zero	4
	.globl	build
	.align 32
	.type	build, @object
	.size	build, 8008
build:
	.zero	8008
	.globl	assign
	.align 32
	.type	assign, @object
	.size	assign, 4004
assign:
	.zero	4004
	.globl	assign2
	.align 32
	.type	assign2, @object
	.size	assign2, 4004
assign2:
	.zero	4004
	.globl	prev
	.align 32
	.type	prev, @object
	.size	prev, 4008004
prev:
	.zero	4008004
	.globl	route
	.align 32
	.type	route, @object
	.size	route, 88176088
route:
	.zero	88176088
	.section	.rodata
.LC0:
	.string	"%d "
	.text
	.globl	backtrack
	.type	backtrack, @function
backtrack:
.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
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	movl	-24(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	prev(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	movl	-20(%rbp), %eax
	cmpl	-24(%rbp), %eax
	je	.L5
	movl	-4(%rbp), %eax
	cmpl	-20(%rbp), %eax
	jne	.L4
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L1
.L4:
	movl	-4(%rbp), %edx
	movl	-20(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	-24(%rbp), %edx
	movl	-4(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	jmp	.L1
.L5:
	nop
.L1:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	backtrack, .-backtrack
	.section	.rodata
.LC1:
	.string	"%d %d %d"
.LC4:
	.string	"%d"
.LC5:
	.string	"%d %d"
.LC6:
	.string	"%d\n"
.LC7:
	.string	"NA"
	.text
	.globl	main
	.type	main, @function
main:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	jmp	.L7
.L32:
	movl	$0, i(%rip)
	jmp	.L8
.L9:
	movl	i(%rip), %eax
	cltq
	salq	$3, %rax
	leaq	4(%rax), %rdx
	leaq	build(%rip), %rax
	leaq	(%rdx,%rax), %rcx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	addq	%rax, %rdx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rsi
	leaq	assign(%rip), %rax
	addq	%rsi, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	i(%rip), %eax
	movslq	%edx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	assign2(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L8:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L9
	movl	$0, i(%rip)
	jmp	.L10
.L15:
	movl	i(%rip), %eax
	movl	%eax, j(%rip)
	jmp	.L11
.L14:
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%esi, %edi
	imull	%eax, %edi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	imull	%esi, %eax
	addl	%edi, %eax
	movl	%eax, l(%rip)
	movl	l(%rip), %eax
	cmpl	$2500, %eax
	jg	.L12
	movl	l(%rip), %eax
	pxor	%xmm3, %xmm3
	cvtsi2sdl	%eax, %xmm3
	movq	%xmm3, %rax
	movl	i(%rip), %ebx
	movl	j(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	l(%rip), %eax
	pxor	%xmm4, %xmm4
	cvtsi2sdl	%eax, %xmm4
	movq	%xmm4, %rax
	movl	j(%rip), %ebx
	movl	i(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	i(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	j(%rip), %edx
	movl	i(%rip), %ecx
	movl	j(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	jmp	.L13
.L12:
	movl	i(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
	movl	j(%rip), %eax
	movl	i(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
.L13:
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L11:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L14
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L10:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L15
	movl	$1, l(%rip)
	jmp	.L16
.L25:
	movl	$0, i(%rip)
	jmp	.L17
.L24:
	movl	$0, j(%rip)
	jmp	.L18
.L23:
	movl	l(%rip), %eax
	leal	-1(%rax), %r8d
	movl	i(%rip), %esi
	movl	j(%rip), %edi
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%edi, %r9
	movslq	%r8d, %rdi
	movslq	%esi, %rsi
	imulq	$1002001, %rdi, %rdi
	imulq	$1001, %rsi, %rsi
	addq	%rdi, %rsi
	addq	%r9, %rsi
	leaq	0(,%rsi,8), %rdi
	leaq	route(%rip), %rsi
	movsd	(%rdi,%rsi), %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	$0, k(%rip)
	jmp	.L19
.L22:
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm2
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	addsd	%xmm2, %xmm1
	comisd	%xmm1, %xmm0
	jbe	.L20
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	addsd	%xmm1, %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	k(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
.L20:
	movl	k(%rip), %eax
	addl	$1, %eax
	movl	%eax, k(%rip)
.L19:
	movl	k(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L22
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L18:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L23
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L17:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L24
	movl	l(%rip), %eax
	addl	$1, %eax
	movl	%eax, l(%rip)
.L16:
	movl	l(%rip), %eax
	pxor	%xmm0, %xmm0
	cvtsi2sdl	%eax, %xmm0
	movq	.LC3(%rip), %rax
	movapd	%xmm0, %xmm1
	movq	%rax, %xmm0
	call	pow@PLT
	movl	n(%rip), %eax
	subl	$1, %eax
	pxor	%xmm1, %xmm1
	cvtsi2sdl	%eax, %xmm1
	comisd	%xmm0, %xmm1
	ja	.L25
	movl	l(%rip), %eax
	subl	$1, %eax
	movl	%eax, l(%rip)
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	jmp	.L26
.L31:
	leaq	y(%rip), %rax
	movq	%rax, %rdx
	leaq	x(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC5(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	x(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, x(%rip)
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, y(%rip)
	movl	x(%rip), %edx
	movl	y(%rip), %eax
	cmpl	%eax, %edx
	jne	.L27
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L27:
	movl	l(%rip), %edx
	movl	x(%rip), %eax
	movl	y(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movsd	.LC2(%rip), %xmm0
	comisd	%xmm1, %xmm0
	jbe	.L36
	movl	y(%rip), %edx
	movl	x(%rip), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L36:
	leaq	.LC7(%rip), %rax
	movq	%rax, %rdi
	call	puts@PLT
.L28:
	movl	m(%rip), %eax
	subl	$1, %eax
	movl	%eax, m(%rip)
.L26:
	movl	m(%rip), %eax
	testl	%eax, %eax
	jg	.L31
.L7:
	leaq	n(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	n(%rip), %edx
	imull	%edx, %eax
	testl	%eax, %eax
	jne	.L32
	movl	$0, %eax
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	main, .-main
	.section	.rodata
	.align 8
.LC2:
	.long	-8388608
	.long	1104006500
	.align 8
.LC3:
	.long	0
	.long	1073741824
	.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	i
	.bss
	.align 4
	.type	i, @object
	.size	i, 4
i:
	.zero	4
	.globl	j
	.align 4
	.type	j, @object
	.size	j, 4
j:
	.zero	4
	.globl	k
	.align 4
	.type	k, @object
	.size	k, 4
k:
	.zero	4
	.globl	n
	.align 4
	.type	n, @object
	.size	n, 4
n:
	.zero	4
	.globl	m
	.align 4
	.type	m, @object
	.size	m, 4
m:
	.zero	4
	.globl	l
	.align 4
	.type	l, @object
	.size	l, 4
l:
	.zero	4
	.globl	x
	.align 4
	.type	x, @object
	.size	x, 4
x:
	.zero	4
	.globl	y
	.align 4
	.type	y, @object
	.size	y, 4
y:
	.zero	4
	.globl	build
	.align 32
	.type	build, @object
	.size	build, 8008
build:
	.zero	8008
	.globl	assign
	.align 32
	.type	assign, @object
	.size	assign, 4004
assign:
	.zero	4004
	.globl	assign2
	.align 32
	.type	assign2, @object
	.size	assign2, 4004
assign2:
	.zero	4004
	.globl	prev
	.align 32
	.type	prev, @object
	.size	prev, 4008004
prev:
	.zero	4008004
	.globl	route
	.align 32
	.type	route, @object
	.size	route, 88176088
route:
	.zero	88176088
	.section	.rodata
.LC0:
	.string	"%d "
	.text
	.globl	backtrack
	.type	backtrack, @function
backtrack:
.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
	movl	%edi, -20(%rbp)
	movl	%esi, -24(%rbp)
	movl	-24(%rbp), %eax
	movslq	%eax, %rdx
	movl	-20(%rbp), %eax
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,4), %rdx
	leaq	prev(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, -4(%rbp)
	movl	-20(%rbp), %eax
	cmpl	-24(%rbp), %eax
	je	.L5
	movl	-4(%rbp), %eax
	cmpl	-20(%rbp), %eax
	jne	.L4
	movl	-20(%rbp), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC0(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L1
.L4:
	movl	-4(%rbp), %edx
	movl	-20(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	-24(%rbp), %edx
	movl	-4(%rbp), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	jmp	.L1
.L5:
	nop
.L1:
	leave
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE6:
	.size	backtrack, .-backtrack
	.section	.rodata
.LC1:
	.string	"%d %d %d"
.LC4:
	.string	"%d"
.LC5:
	.string	"%d %d"
.LC6:
	.string	"%d\n"
.LC7:
	.string	"NA"
	.text
	.globl	main
	.type	main, @function
main:
.LFB7:
	.cfi_startproc
	endbr64
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	movq	%rsp, %rbp
	.cfi_def_cfa_register 6
	pushq	%r12
	pushq	%rbx
	.cfi_offset 12, -24
	.cfi_offset 3, -32
	jmp	.L7
.L32:
	movl	$0, i(%rip)
	jmp	.L8
.L9:
	movl	i(%rip), %eax
	cltq
	salq	$3, %rax
	leaq	4(%rax), %rdx
	leaq	build(%rip), %rax
	leaq	(%rdx,%rax), %rcx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	addq	%rax, %rdx
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rsi
	leaq	assign(%rip), %rax
	addq	%rsi, %rax
	movq	%rax, %rsi
	leaq	.LC1(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %edx
	movl	i(%rip), %eax
	movslq	%edx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	assign2(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L8:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L9
	movl	$0, i(%rip)
	jmp	.L10
.L15:
	movl	i(%rip), %eax
	movl	%eax, j(%rip)
	jmp	.L11
.L14:
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%esi, %edi
	imull	%eax, %edi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	movl	%eax, %esi
	movl	i(%rip), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	4+build(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	4+build(%rip), %rdx
	movl	(%rcx,%rdx), %edx
	subl	%edx, %eax
	imull	%esi, %eax
	addl	%edi, %eax
	movl	%eax, l(%rip)
	movl	l(%rip), %eax
	cmpl	$2500, %eax
	jg	.L12
	movl	l(%rip), %eax
	pxor	%xmm3, %xmm3
	cvtsi2sdl	%eax, %xmm3
	movq	%xmm3, %rax
	movl	i(%rip), %ebx
	movl	j(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	l(%rip), %eax
	pxor	%xmm4, %xmm4
	cvtsi2sdl	%eax, %xmm4
	movq	%xmm4, %rax
	movl	j(%rip), %ebx
	movl	i(%rip), %r12d
	movq	%rax, %xmm0
	call	sqrt@PLT
	movq	%xmm0, %rax
	movslq	%r12d, %rcx
	movslq	%ebx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,8), %rcx
	leaq	route(%rip), %rdx
	movq	%rax, (%rcx,%rdx)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	i(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	movl	j(%rip), %edx
	movl	i(%rip), %ecx
	movl	j(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
	jmp	.L13
.L12:
	movl	i(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
	movl	j(%rip), %eax
	movl	i(%rip), %edx
	movslq	%edx, %rdx
	cltq
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	.LC2(%rip), %xmm0
	movsd	%xmm0, (%rdx,%rax)
.L13:
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L11:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L14
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L10:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L15
	movl	$1, l(%rip)
	jmp	.L16
.L25:
	movl	$0, i(%rip)
	jmp	.L17
.L24:
	movl	$0, j(%rip)
	jmp	.L18
.L23:
	movl	l(%rip), %eax
	leal	-1(%rax), %r8d
	movl	i(%rip), %esi
	movl	j(%rip), %edi
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%edi, %r9
	movslq	%r8d, %rdi
	movslq	%esi, %rsi
	imulq	$1002001, %rdi, %rdi
	imulq	$1001, %rsi, %rsi
	addq	%rdi, %rsi
	addq	%r9, %rsi
	leaq	0(,%rsi,8), %rdi
	leaq	route(%rip), %rsi
	movsd	(%rdi,%rsi), %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	$0, k(%rip)
	jmp	.L19
.L22:
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm2
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	addsd	%xmm2, %xmm1
	comisd	%xmm1, %xmm0
	jbe	.L20
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	i(%rip), %eax
	movl	k(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movl	l(%rip), %eax
	leal	-1(%rax), %ecx
	movl	k(%rip), %eax
	movl	j(%rip), %edx
	movslq	%edx, %rsi
	movslq	%ecx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rsi, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm0
	movl	l(%rip), %edx
	movl	i(%rip), %eax
	movl	j(%rip), %ecx
	addsd	%xmm1, %xmm0
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	%xmm0, (%rdx,%rax)
	movl	i(%rip), %edx
	movl	j(%rip), %ecx
	movl	k(%rip), %eax
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	imulq	$1001, %rdx, %rdx
	addq	%rcx, %rdx
	leaq	0(,%rdx,4), %rcx
	leaq	prev(%rip), %rdx
	movl	%eax, (%rcx,%rdx)
.L20:
	movl	k(%rip), %eax
	addl	$1, %eax
	movl	%eax, k(%rip)
.L19:
	movl	k(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L22
	movl	j(%rip), %eax
	addl	$1, %eax
	movl	%eax, j(%rip)
.L18:
	movl	j(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L23
	movl	i(%rip), %eax
	addl	$1, %eax
	movl	%eax, i(%rip)
.L17:
	movl	i(%rip), %edx
	movl	n(%rip), %eax
	cmpl	%eax, %edx
	jl	.L24
	movl	l(%rip), %eax
	addl	$1, %eax
	movl	%eax, l(%rip)
.L16:
	movl	l(%rip), %eax
	pxor	%xmm0, %xmm0
	cvtsi2sdl	%eax, %xmm0
	movq	.LC3(%rip), %rax
	movapd	%xmm0, %xmm1
	movq	%rax, %xmm0
	call	pow@PLT
	movl	n(%rip), %eax
	subl	$1, %eax
	pxor	%xmm1, %xmm1
	cvtsi2sdl	%eax, %xmm1
	comisd	%xmm0, %xmm1
	ja	.L25
	movl	l(%rip), %eax
	subl	$1, %eax
	movl	%eax, l(%rip)
	leaq	m(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	jmp	.L26
.L31:
	leaq	y(%rip), %rax
	movq	%rax, %rdx
	leaq	x(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC5(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	x(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, x(%rip)
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign2(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, y(%rip)
	movl	x(%rip), %edx
	movl	y(%rip), %eax
	cmpl	%eax, %edx
	jne	.L27
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L27:
	movl	l(%rip), %edx
	movl	x(%rip), %eax
	movl	y(%rip), %ecx
	movslq	%ecx, %rcx
	movslq	%edx, %rdx
	cltq
	imulq	$1002001, %rdx, %rdx
	imulq	$1001, %rax, %rax
	addq	%rdx, %rax
	addq	%rcx, %rax
	leaq	0(,%rax,8), %rdx
	leaq	route(%rip), %rax
	movsd	(%rdx,%rax), %xmm1
	movsd	.LC2(%rip), %xmm0
	comisd	%xmm1, %xmm0
	jbe	.L36
	movl	y(%rip), %edx
	movl	x(%rip), %eax
	movl	%edx, %esi
	movl	%eax, %edi
	call	backtrack
	movl	y(%rip), %eax
	cltq
	leaq	0(,%rax,4), %rdx
	leaq	assign(%rip), %rax
	movl	(%rdx,%rax), %eax
	movl	%eax, %esi
	leaq	.LC6(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	printf@PLT
	jmp	.L28
.L36:
	leaq	.LC7(%rip), %rax
	movq	%rax, %rdi
	call	puts@PLT
.L28:
	movl	m(%rip), %eax
	subl	$1, %eax
	movl	%eax, m(%rip)
.L26:
	movl	m(%rip), %eax
	testl	%eax, %eax
	jg	.L31
.L7:
	leaq	n(%rip), %rax
	movq	%rax, %rsi
	leaq	.LC4(%rip), %rax
	movq	%rax, %rdi
	movl	$0, %eax
	call	__isoc99_scanf@PLT
	movl	n(%rip), %edx
	imull	%edx, %eax
	testl	%eax, %eax
	jne	.L32
	movl	$0, %eax
	popq	%rbx
	popq	%r12
	popq	%rbp
	.cfi_def_cfa 7, 8
	ret
	.cfi_endproc
.LFE7:
	.size	main, .-main
	.section	.rodata
	.align 8
.LC2:
	.long	-8388608
	.long	1104006500
	.align 8
.LC3:
	.long	0
	.long	1073741824
	.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:
