#include <iostream>
#include <cstdlib>
#include <stdlib.h>
#include <ctime>
#include <queue>

using namespace std;

short iterative_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix);
short recursive_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix);
short recursive_bfs_helper(short **matrix, unsigned long long N, short target, unsigned long long x, unsigned long long y, bool **visited_matrix);

void kernel_bfs_wrapper(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target);
__global__ void bfs_kernel(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target);

int main()
{
  // default size is 100
  unsigned long long N = 100;
  int *h_found_idx, *found_idx;
  short **seq_matrix,
  *h_matrix,
  *cuda_matrix,
  *seq_result,
  *cuda_result,
  target;
  int *mtx;
  bool **visited_matrix;

  // Declare timers
  float cuda_elapsed_time;
  cudaEvent_t cuda_start, cuda_stop;
  double seq_start, seq_stop, seq_iter_elapsed_time, seq_recur_elapsed_time;

  cout << "Enter N (NxN matrix): ";
  cin >> N;

  cout << "Enter target integer [0 to 100]: ";
  cin >> target;

  // allocate memory for seq
  seq_matrix = (short**) malloc(N * sizeof(short*));
  visited_matrix = (bool**) malloc(N * sizeof(bool*));
  seq_result = (short*) malloc(sizeof(short));
  h_found_idx = (int*) malloc(sizeof(int));
  h_matrix = (short*) malloc(N * N * sizeof(short));
  srand(time(0));
  // set matrix to random shortegers from 0 to 100
  for (unsigned long long i = 0; i < N; i++) {
    seq_matrix[i] = (short*) malloc(N * sizeof(short));
    visited_matrix[i] = (bool*) malloc(N * sizeof(bool));
    for (unsigned long long j = 0; j < N; j++) {
      seq_matrix[i][j] = rand() % 101;
      visited_matrix[i][j] = false;
      h_matrix[i*N + j] = seq_matrix[i][j];
    }
  }
  //cout << "random numbers generated" << endl;

  // allocate memory for cuda
  cudaMalloc((void **) &cuda_matrix, N * N * sizeof(short));
  //cudaMallocPitch((void**)&cuda_matrix, &pitch, N * sizeof(short), N);
  //cudaMallocPitch((void**)&cuda_visited_matrix, &pitch_visited, N * sizeof(short), N);
  //for (unsigned long long i = 0; i < N; i++) {
  //  cudaMalloc(&cuda_matrix[i], N * sizeof(short));
  //}
  cudaMalloc((void**)&found_idx, sizeof(int));
  //cudaMalloc((void**)&cuda_result, sizeof(short));
  cudaMalloc((void**)&mtx, sizeof(int));
  //cout << "cuda malloc good" << endl;

  // set values of cuda target to -1 (not found)
  // set values of mtx target to 0
  cudaMemset(found_idx, 0, sizeof(int));
  //cudaMemset(cuda_result, -1, sizeof(short));
  cudaMemset(mtx, 0, sizeof(short));

  // set up timing variables
  cudaEventCreate(&cuda_start);
  cudaEventCreate(&cuda_stop);
  //for (unsigned long long i = 0; i < N; i++) {
  //  cudaMemcpy(cuda_matrix[i], seq_matrix[i], N * sizeof(short), cudaMemcpyHostToDevice);
    //cudaMemcpy(cuda_visited_matrix[i], visited_matrix[i], N * sizeof(bool), cudaMemcpyHostToDevice);
  //}
  cudaMemcpy(cuda_matrix, h_matrix, N * N * sizeof(short), cudaMemcpyHostToDevice);
  //cudaMemcpy2DToArray(cuda_matrix, pitch, seq_matrix, N*sizeof(short), N*sizeof(short), N, cudaMemcpyHostToDevice);
  //cudaMemcpy2DToArray(cuda_visited_matrix, pitch_visited, visited_matrix, N*sizeof(bool), N*sizeof(bool), N, cudaMemcpyHostToDevice);
  //cudaMemcpy(cuda_matrix, seq_matrix, N * sizeof(short*), cudaMemcpyHostToDevice);
  //cudaMemcpy(cuda_visited_matrix, visited_matrix, N * sizeof(bool*), cudaMemcpyHostToDevice);
  // copy from host to device
  cudaEventRecord(cuda_start, 0);

  // START CUDA
  kernel_bfs_wrapper(cuda_matrix, found_idx, mtx, N, target);

  // copy from device to host
  cudaEventRecord(cuda_stop, 0);
  cudaEventSynchronize(cuda_stop);
  cudaEventElapsedTime(&cuda_elapsed_time, cuda_start, cuda_stop);
  //cudaMemcpy2D(seq_result, sizeof(short)*N, cuda_result, pitch, sizeof(short)*N, N, cudaMemcpyDeviceToHost);
  //cudaMemcpy(seq_result, cuda_result, sizeof(short), cudaMemcpyDeviceToHost);
  cudaMemcpy(h_found_idx, found_idx, sizeof(int), cudaMemcpyDeviceToHost);

  // destroy timers
  cudaEventDestroy(cuda_start);
  cudaEventDestroy(cuda_stop);

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << h_matrix[*h_found_idx] << endl;
  cout << "[CUDA] Elapsed time: " << cuda_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  cout << endl;

  cout << "Starting sequential iterative approach." << endl;

  // reset visited_matrix back to false
  for (unsigned long long i = 0; i < N; i++) {
    for (unsigned long long j = 0; j < N; j++) {
      visited_matrix[i][j] = false;
    }
  }

  seq_start = (double) clock();

  // call iterative bfs
  *seq_result = -1;
  *seq_result = iterative_bfs(seq_matrix, N, target, visited_matrix);

  seq_stop = (double) clock();
  seq_iter_elapsed_time = (double) 1000.0*((double)(seq_stop - seq_start))/CLOCKS_PER_SEC;

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << *seq_result << endl;
  cout << "[SEQUENTIAL - Iterative] Elapsed time: " << seq_iter_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  cout << "Starting sequential recursive approach." << endl;

  // reset visited_matrix back to false
  for (unsigned long long i = 0; i < N; i++) {
    for (unsigned long long j = 0; j < N; j++) {
      visited_matrix[i][j] = false;
    }
  }

  seq_start = (double) clock();

  // call recursive bfs
  *seq_result = -1;
  *seq_result = recursive_bfs(seq_matrix, N, target, visited_matrix);

  seq_stop = (double) clock();
  seq_recur_elapsed_time = (double) 1000.0*((double)(seq_stop - seq_start))/CLOCKS_PER_SEC;

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << *seq_result << endl;
  cout << "[SEQUENTIAL - Recursive] Elapsed time: " << seq_recur_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  // free and cuda free
  for (unsigned long long i = 0; i < N; i++) {
    free(seq_matrix[i]);
    free(visited_matrix[i]);
  }
  free(seq_matrix);
  free(visited_matrix);
  free(h_matrix);
  free(seq_result);
  free(h_found_idx);
  cudaFree(cuda_matrix);
  cudaFree(mtx);
  cudaFree(found_idx);
  //cudaFree(cuda_result);

  return 0;
}

short iterative_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix) {
  // check initial spot
  if (matrix[0][0] == target)
    return matrix[0][0];

  visited_matrix[0][0] = true;
  queue<unsigned long long> qx;
  queue<unsigned long long> qy;
  qx.push(0);
  qy.push(0);
  while (!qx.empty()) {
    unsigned long long x = qx.front();
    unsigned long long y = qy.front();
    qx.pop();
    qy.pop();
    visited_matrix[x][y] = true;
    if (matrix[x][y] == target) {
      return matrix[x][y];
    }
    // check right then check down
    if (x + 1 < N && !visited_matrix[x+1][y]) {
      qx.push(x+1);
      qy.push(y);
    }
    if (y + 1 < N && !visited_matrix[x][y+1]) {
      qx.push(x);
      qy.push(y+1);
    }
  }
  return -1;
}

short recursive_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix) {
  // check initial spot
  if (matrix[0][0] == target)
    return matrix[0][0];

  visited_matrix[0][0] = true;

  return recursive_bfs_helper(matrix, N, target, 0, 0, visited_matrix);
}

short recursive_bfs_helper(short **matrix, unsigned long long N, short target, unsigned long long x, unsigned long long y, bool **visited_matrix) {
  // check right
  if (x+1 < N && matrix[x+1][y] == target)
    return matrix[x+1][y];
  // check down
  if (y+1 < N && matrix[x][y+1] == target)
    return matrix[x][y+1];

  // traverse to right first, then down
  short right = -1;
  short down = -1;

  if (x+1 < N && !visited_matrix[x+1][y]) {
    visited_matrix[x+1][y] = true;
    right = recursive_bfs_helper(matrix, N, target, x+1, y, visited_matrix);
  }
  // if found in right, then return right
  if (right != -1)
    return right;

  if (y+1 < N && !visited_matrix[x][y+1]) {
    visited_matrix[x][y+1] = true;
    down = recursive_bfs_helper(matrix, N, target, x, y+1, visited_matrix);
  }
  // if found in down, then return down
  if (down != -1)
    return down;

  // otherwise, nothing has been found.
  return -1;
}

void kernel_bfs_wrapper(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target)
{
  // 1 dimensional
  dim3 blockSize = (256);
  dim3 gridSize = ((N*N + (2048 - 1))/(2048));
  bfs_kernel<<< gridSize, blockSize >>>(matrix, found_idx, mtx, N, target);
}

__global__ void bfs_kernel(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target)
{
  int idx = threadIdx.x + blockDim.x * blockIdx.x;
  //unsigned long long idy = threadIdx.y + blockDim.y + blockIdx.y; 

  if (idx >= N*N) {
    return;
  }
  //printf("%d\n", matrix[idx]);
  //short *row = (short*) ((char*) matrix + ;
  // found!!
  if (matrix[idx] == target) {
    //printf("%d\n", matrix[idx]);
    //while(atomicCAS(mtx, 0, 1) != 0);
    //printf("Set\n");
    //*result = matrix[idx];
    atomicMax(found_idx, idx);
    //printf("found id: %d\n", *found_idx);
    //printf("id: %d\n", idx);
    //printf("Result: %d\n", *result);
    //atomicExch(mtx, 0);
    //printf("Keep going\n");
  }
}

	.file	"tmpxft_002c406a_00000000-6_bfs.cudafe1.cpp"
	.text
#APP
	.globl _ZSt21ios_base_library_initv

#NO_APP
	.type	_ZL26__cudaUnregisterBinaryUtilv, @function
_ZL26__cudaUnregisterBinaryUtilv:
.LFB4272:
	.cfi_startproc
	endbr64
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	jmp	__cudaUnregisterFatBinary@PLT
	.cfi_endproc
.LFE4272:
	.size	_ZL26__cudaUnregisterBinaryUtilv, .-_ZL26__cudaUnregisterBinaryUtilv
	.align 2
	.type	_ZNSolsEPFRSoS_E.isra.0, @function
_ZNSolsEPFRSoS_E.isra.0:
.LFB5072:
	.cfi_startproc
	jmp	*%rsi
	.cfi_endproc
.LFE5072:
	.size	_ZNSolsEPFRSoS_E.isra.0, .-_ZNSolsEPFRSoS_E.isra.0
	.globl	_Z20recursive_bfs_helperPPsysyyPPb
	.type	_Z20recursive_bfs_helperPPsysyyPPb, @function
_Z20recursive_bfs_helperPPsysyyPPb:
.LFB4268:
	.cfi_startproc
	endbr64
	pushq	%r14
	.cfi_def_cfa_offset 16
	.cfi_offset 14, -16
	movl	%edx, %eax
	pushq	%r13
	.cfi_def_cfa_offset 24
	.cfi_offset 13, -24
	movq	%rcx, %r13
	incq	%rcx
	pushq	%rbp
	.cfi_def_cfa_offset 32
	.cfi_offset 6, -32
	movl	%edx, %ebp
	subq	$32, %rsp
	.cfi_def_cfa_offset 64
	cmpq	%rsi, %rcx
	jnb	.L4
	movq	(%rdi,%rcx,8), %rdx
	cmpw	%bp, (%rdx,%r8,2)
	je	.L14
.L4:
	leaq	1(%r8), %r14
	cmpq	%rsi, %r14
	jnb	.L6
	movq	(%rdi,%r13,8), %rdx
	cmpw	%bp, (%rdx,%r14,2)
	je	.L14
	cmpq	%rsi, %rcx
	jnb	.L9
.L12:
	movq	(%r9,%rcx,8), %rax
	addq	%r8, %rax
	cmpb	$0, (%rax)
	je	.L8
.L11:
	cmpq	%rsi, %r14
	jb	.L9
	jmp	.L10
.L8:
	movb	$1, (%rax)
	movswl	%bp, %edx
	movq	%r9, 24(%rsp)
	movq	%rsi, 16(%rsp)
	movq	%rdi, 8(%rsp)
	call	_Z20recursive_bfs_helperPPsysyyPPb
	cmpw	$-1, %ax
	jne	.L14
	movq	8(%rsp), %rdi
	movq	16(%rsp), %rsi
	movq	24(%rsp), %r9
	jmp	.L11
.L6:
	cmpq	%rsi, %rcx
	jb	.L12
.L10:
	orl	$-1, %eax
	jmp	.L14
.L9:
	movq	(%r9,%r13,8), %rax
	addq	%r14, %rax
	cmpb	$0, (%rax)
	jne	.L10
	movb	$1, (%rax)
	addq	$32, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 32
	movswl	%bp, %edx
	movq	%r14, %r8
	popq	%rbp
	.cfi_def_cfa_offset 24
	movq	%r13, %rcx
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	jmp	_Z20recursive_bfs_helperPPsysyyPPb
.L14:
	.cfi_restore_state
	addq	$32, %rsp
	.cfi_def_cfa_offset 32
	popq	%rbp
	.cfi_def_cfa_offset 24
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE4268:
	.size	_Z20recursive_bfs_helperPPsysyyPPb, .-_Z20recursive_bfs_helperPPsysyyPPb
	.globl	_Z13recursive_bfsPPsysPPb
	.type	_Z13recursive_bfsPPsysPPb, @function
_Z13recursive_bfsPPsysPPb:
.LFB4267:
	.cfi_startproc
	endbr64
	movq	%rcx, %r9
	movq	(%rdi), %rcx
	movl	%edx, %eax
	cmpw	%dx, (%rcx)
	je	.L19
	movq	(%r9), %rax
	movswl	%dx, %edx
	xorl	%r8d, %r8d
	xorl	%ecx, %ecx
	movb	$1, (%rax)
	jmp	_Z20recursive_bfs_helperPPsysyyPPb
.L19:
	ret
	.cfi_endproc
.LFE4267:
	.size	_Z13recursive_bfsPPsysPPb, .-_Z13recursive_bfsPPsysPPb
	.globl	_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys
	.type	_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys, @function
_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys:
.LFB4294:
	.cfi_startproc
	endbr64
	subq	$168, %rsp
	.cfi_def_cfa_offset 176
	movq	%rdi, 40(%rsp)
	leaq	64(%rsp), %rdi
	movq	%rsi, 32(%rsp)
	leaq	76(%rsp), %rsi
	movq	%rdx, 24(%rsp)
	leaq	48(%rsp), %rdx
	movq	%rcx, 16(%rsp)
	leaq	56(%rsp), %rcx
	movw	%r8w, 12(%rsp)
	movq	%fs:40, %rax
	movq	%rax, 152(%rsp)
	xorl	%eax, %eax
	leaq	40(%rsp), %rax
	movl	$1, 72(%rsp)
	movq	%rax, 112(%rsp)
	leaq	32(%rsp), %rax
	movq	%rax, 120(%rsp)
	leaq	24(%rsp), %rax
	movq	%rax, 128(%rsp)
	leaq	16(%rsp), %rax
	movq	%rax, 136(%rsp)
	leaq	12(%rsp), %rax
	movq	%rax, 144(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 64(%rsp)
	movq	%rax, 76(%rsp)
	movl	$1, 84(%rsp)
	call	__cudaPopCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L20
	pushq	56(%rsp)
	.cfi_def_cfa_offset 184
	leaq	_Z10bfs_kernelPsPiS0_ys(%rip), %rdi
	pushq	56(%rsp)
	.cfi_def_cfa_offset 192
	movq	92(%rsp), %rcx
	movl	100(%rsp), %r8d
	movq	80(%rsp), %rsi
	movl	88(%rsp), %edx
	leaq	128(%rsp), %r9
	call	cudaLaunchKernel@PLT
	popq	%rax
	.cfi_def_cfa_offset 184
	popq	%rdx
	.cfi_def_cfa_offset 176
.L20:
	movq	152(%rsp), %rax
	subq	%fs:40, %rax
	je	.L22
	call	__stack_chk_fail@PLT
.L22:
	addq	$168, %rsp
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE4294:
	.size	_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys, .-_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys
	.globl	_Z10bfs_kernelPsPiS0_ys
	.type	_Z10bfs_kernelPsPiS0_ys, @function
_Z10bfs_kernelPsPiS0_ys:
.LFB4295:
	.cfi_startproc
	endbr64
	movswl	%r8w, %r8d
	jmp	_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys
	.cfi_endproc
.LFE4295:
	.size	_Z10bfs_kernelPsPiS0_ys, .-_Z10bfs_kernelPsPiS0_ys
	.globl	_Z18kernel_bfs_wrapperPsPiS0_ys
	.type	_Z18kernel_bfs_wrapperPsPiS0_ys, @function
_Z18kernel_bfs_wrapperPsPiS0_ys:
.LFB4269:
	.cfi_startproc
	endbr64
	movq	%rcx, %rax
	pushq	%r14
	.cfi_def_cfa_offset 16
	.cfi_offset 14, -16
	xorl	%r9d, %r9d
	movl	%r8d, %r14d
	imulq	%rcx, %rax
	pushq	%r13
	.cfi_def_cfa_offset 24
	.cfi_offset 13, -24
	movq	%rdx, %r13
	movl	$16777217, %edx
	pushq	%r12
	.cfi_def_cfa_offset 32
	.cfi_offset 12, -32
	movq	%rsi, %r12
	xorl	%r8d, %r8d
	salq	$8, %rdx
	pushq	%rbp
	.cfi_def_cfa_offset 40
	.cfi_offset 6, -40
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset 3, -48
	addq	$2047, %rax
	movq	%rcx, %rbx
	movl	$1, %ecx
	shrq	$11, %rax
	subq	$32, %rsp
	.cfi_def_cfa_offset 80
	movl	%eax, 20(%rsp)
	movabsq	$4294967297, %rax
	movq	%rax, 24(%rsp)
	movq	20(%rsp), %rdi
	movl	28(%rsp), %esi
	call	__cudaPushCallConfiguration@PLT
	testl	%eax, %eax
	jne	.L25
	addq	$32, %rsp
	.cfi_remember_state
	.cfi_def_cfa_offset 48
	movswl	%r14w, %r8d
	movq	%rbx, %rcx
	movq	%r13, %rdx
	popq	%rbx
	.cfi_def_cfa_offset 40
	movq	%r12, %rsi
	movq	%rbp, %rdi
	popq	%rbp
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	jmp	_Z37__device_stub__Z10bfs_kernelPsPiS0_ysPsPiS0_ys
.L25:
	.cfi_restore_state
	addq	$32, %rsp
	.cfi_def_cfa_offset 48
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%rbp
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r13
	.cfi_def_cfa_offset 16
	popq	%r14
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE4269:
	.size	_Z18kernel_bfs_wrapperPsPiS0_ys, .-_Z18kernel_bfs_wrapperPsPiS0_ys
	.section	.rodata.str1.1,"aMS",@progbits,1
.LC0:
	.string	"_Z10bfs_kernelPsPiS0_ys"
	.section	.text.startup,"ax",@progbits
	.type	_ZL24__sti____cudaRegisterAllv, @function
_ZL24__sti____cudaRegisterAllv:
.LFB4297:
	.cfi_startproc
	endbr64
	pushq	%rax
	.cfi_def_cfa_offset 16
	leaq	_ZL15__fatDeviceText(%rip), %rdi
	call	__cudaRegisterFatBinary@PLT
	pushq	$0
	.cfi_def_cfa_offset 24
	xorl	%r9d, %r9d
	orl	$-1, %r8d
	pushq	$0
	.cfi_def_cfa_offset 32
	leaq	.LC0(%rip), %rdx
	movq	%rax, %rdi
	leaq	_Z10bfs_kernelPsPiS0_ys(%rip), %rsi
	pushq	$0
	.cfi_def_cfa_offset 40
	movq	%rdx, %rcx
	pushq	$0
	.cfi_def_cfa_offset 48
	movq	%rax, _ZL20__cudaFatCubinHandle(%rip)
	call	__cudaRegisterFunction@PLT
	movq	_ZL20__cudaFatCubinHandle(%rip), %rdi
	addq	$32, %rsp
	.cfi_def_cfa_offset 16
	call	__cudaRegisterFatBinaryEnd@PLT
	leaq	_ZL26__cudaUnregisterBinaryUtilv(%rip), %rdi
	popq	%rdx
	.cfi_def_cfa_offset 8
	jmp	atexit@PLT
	.cfi_endproc
.LFE4297:
	.size	_ZL24__sti____cudaRegisterAllv, .-_ZL24__sti____cudaRegisterAllv
	.section	.init_array,"aw"
	.align 8
	.quad	_ZL24__sti____cudaRegisterAllv
	.section	.text._ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv,"axG",@progbits,_ZNSt5queueIySt5dequeIySaIyEEEC5IS2_vEEv,comdat
	.align 2
	.weak	_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv
	.type	_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv, @function
_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv:
.LFB4607:
	.cfi_startproc
	.cfi_personality 0x9b,DW.ref.__gxx_personality_v0
	.cfi_lsda 0x1b,.LLSDA4607
	endbr64
	xorl	%esi, %esi
	pushq	%rbp
	.cfi_def_cfa_offset 16
	.cfi_offset 6, -16
	pushq	%rbx
	.cfi_def_cfa_offset 24
	.cfi_offset 3, -24
	movq	%rdi, %rbx
	pushq	%rcx
	.cfi_def_cfa_offset 32
	movq	%rsi, (%rdi)
	movq	%rsi, 16(%rdi)
	movq	%rsi, 24(%rdi)
	movq	%rsi, 32(%rdi)
	movq	%rsi, 40(%rdi)
	movq	%rsi, 48(%rdi)
	movq	%rsi, 56(%rdi)
	movq	%rsi, 64(%rdi)
	movq	%rsi, 72(%rdi)
	movq	$8, 8(%rdi)
	movl	$64, %edi
.LEHB0:
	call	_Znwm@PLT
.LEHE0:
	movq	8(%rbx), %rdx
	movl	$512, %edi
	movq	%rax, (%rbx)
	leaq	-4(,%rdx,4), %rdx
	andq	$-8, %rdx
	leaq	(%rax,%rdx), %rbp
.LEHB1:
	call	_Znwm@PLT
.LEHE1:
	leaq	512(%rax), %rdx
	movq	%rax, 0(%rbp)
	movq	%rbp, 40(%rbx)
	movq	%rax, 24(%rbx)
	movq	%rdx, 32(%rbx)
	movq	%rbp, 72(%rbx)
	movq	%rax, 56(%rbx)
	movq	%rdx, 64(%rbx)
	movq	%rax, 16(%rbx)
	movq	%rax, 48(%rbx)
	popq	%rdx
	.cfi_remember_state
	.cfi_def_cfa_offset 24
	popq	%rbx
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	ret
.L35:
	.cfi_restore_state
	endbr64
	movq	%rax, %rdi
.L31:
	call	__cxa_begin_catch@PLT
.LEHB2:
	call	__cxa_rethrow@PLT
.LEHE2:
.L36:
	endbr64
	movq	%rax, %rbp
.L32:
	call	__cxa_end_catch@PLT
	movq	%rbp, %rdi
	call	__cxa_begin_catch@PLT
	movq	8(%rbx), %rax
	movq	(%rbx), %rdi
	leaq	0(,%rax,8), %rsi
	call	_ZdlPvm@PLT
	xorl	%eax, %eax
	movq	%rax, (%rbx)
	movq	%rax, 8(%rbx)
.LEHB3:
	call	__cxa_rethrow@PLT
.LEHE3:
.L34:
	endbr64
	movq	%rax, %rbx
.L33:
	call	__cxa_end_catch@PLT
	movq	%rbx, %rdi
.LEHB4:
	call	_Unwind_Resume@PLT
.LEHE4:
	.cfi_endproc
.LFE4607:
	.globl	__gxx_personality_v0
	.section	.gcc_except_table._ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv,"aG",@progbits,_ZNSt5queueIySt5dequeIySaIyEEEC5IS2_vEEv,comdat
	.align 4
.LLSDA4607:
	.byte	0xff
	.byte	0x9b
	.uleb128 .LLSDATT4607-.LLSDATTD4607
.LLSDATTD4607:
	.byte	0x1
	.uleb128 .LLSDACSE4607-.LLSDACSB4607
.LLSDACSB4607:
	.uleb128 .LEHB0-.LFB4607
	.uleb128 .LEHE0-.LEHB0
	.uleb128 0
	.uleb128 0
	.uleb128 .LEHB1-.LFB4607
	.uleb128 .LEHE1-.LEHB1
	.uleb128 .L35-.LFB4607
	.uleb128 0x1
	.uleb128 .LEHB2-.LFB4607
	.uleb128 .LEHE2-.LEHB2
	.uleb128 .L36-.LFB4607
	.uleb128 0x3
	.uleb128 .LEHB3-.LFB4607
	.uleb128 .LEHE3-.LEHB3
	.uleb128 .L34-.LFB4607
	.uleb128 0
	.uleb128 .LEHB4-.LFB4607
	.uleb128 .LEHE4-.LEHB4
	.uleb128 0
	.uleb128 0
.LLSDACSE4607:
	.byte	0x1
	.byte	0
	.byte	0
	.byte	0x7d
	.align 4
	.long	0

.LLSDATT4607:
	.section	.text._ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv,"axG",@progbits,_ZNSt5queueIySt5dequeIySaIyEEEC5IS2_vEEv,comdat
	.size	_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv, .-_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv
	.weak	_ZNSt5queueIySt5dequeIySaIyEEEC1IS2_vEEv
	.set	_ZNSt5queueIySt5dequeIySaIyEEEC1IS2_vEEv,_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv
	.section	.text._ZNSt11_Deque_baseIySaIyEED2Ev,"axG",@progbits,_ZNSt11_Deque_baseIySaIyEED5Ev,comdat
	.align 2
	.weak	_ZNSt11_Deque_baseIySaIyEED2Ev
	.type	_ZNSt11_Deque_baseIySaIyEED2Ev, @function
_ZNSt11_Deque_baseIySaIyEED2Ev:
.LFB4768:
	.cfi_startproc
	endbr64
	cmpq	$0, (%rdi)
	je	.L39
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	72(%rdi), %rax
	movq	%rdi, %rbx
	movq	40(%rdi), %rbp
	leaq	8(%rax), %r12
.L41:
	cmpq	%r12, %rbp
	jnb	.L46
	movq	0(%rbp), %rdi
	movl	$512, %esi
	addq	$8, %rbp
	call	_ZdlPvm@PLT
	jmp	.L41
.L46:
	movq	8(%rbx), %rax
	movq	(%rbx), %rdi
	popq	%rbx
	.cfi_restore 3
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_restore 6
	.cfi_def_cfa_offset 16
	leaq	0(,%rax,8), %rsi
	popq	%r12
	.cfi_restore 12
	.cfi_def_cfa_offset 8
	jmp	_ZdlPvm@PLT
.L39:
	ret
	.cfi_endproc
.LFE4768:
	.size	_ZNSt11_Deque_baseIySaIyEED2Ev, .-_ZNSt11_Deque_baseIySaIyEED2Ev
	.weak	_ZNSt11_Deque_baseIySaIyEED1Ev
	.set	_ZNSt11_Deque_baseIySaIyEED1Ev,_ZNSt11_Deque_baseIySaIyEED2Ev
	.section	.text._ZNSt5dequeIySaIyEE9pop_frontEv,"axG",@progbits,_ZNSt5dequeIySaIyEE9pop_frontEv,comdat
	.align 2
	.weak	_ZNSt5dequeIySaIyEE9pop_frontEv
	.type	_ZNSt5dequeIySaIyEE9pop_frontEv, @function
_ZNSt5dequeIySaIyEE9pop_frontEv:
.LFB4778:
	.cfi_startproc
	endbr64
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset 3, -16
	movq	32(%rdi), %rcx
	movq	%rdi, %rbx
	movq	16(%rdi), %rax
	leaq	-8(%rcx), %rdx
	cmpq	%rdx, %rax
	je	.L48
	addq	$8, %rax
	jmp	.L49
.L48:
	movq	24(%rdi), %rdi
	movl	$512, %esi
	call	_ZdlPvm@PLT
	movq	40(%rbx), %rax
	leaq	8(%rax), %rdx
	movq	8(%rax), %rax
	movq	%rdx, 40(%rbx)
	leaq	512(%rax), %rdx
	movq	%rax, 24(%rbx)
	movq	%rdx, 32(%rbx)
.L49:
	movq	%rax, 16(%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE4778:
	.size	_ZNSt5dequeIySaIyEE9pop_frontEv, .-_ZNSt5dequeIySaIyEE9pop_frontEv
	.section	.text._ZStmiRKSt15_Deque_iteratorIyRyPyES4_,"axG",@progbits,_ZStmiRKSt15_Deque_iteratorIyRyPyES4_,comdat
	.weak	_ZStmiRKSt15_Deque_iteratorIyRyPyES4_
	.type	_ZStmiRKSt15_Deque_iteratorIyRyPyES4_, @function
_ZStmiRKSt15_Deque_iteratorIyRyPyES4_:
.LFB5021:
	.cfi_startproc
	endbr64
	movq	24(%rdi), %rdx
	movq	%rdx, %rax
	subq	24(%rsi), %rax
	sarq	$3, %rax
	cmpq	$1, %rdx
	movq	(%rdi), %rdx
	adcq	$-1, %rax
	subq	8(%rdi), %rdx
	sarq	$3, %rdx
	salq	$6, %rax
	addq	%rdx, %rax
	movq	16(%rsi), %rdx
	subq	(%rsi), %rdx
	sarq	$3, %rdx
	addq	%rdx, %rax
	ret
	.cfi_endproc
.LFE5021:
	.size	_ZStmiRKSt15_Deque_iteratorIyRyPyES4_, .-_ZStmiRKSt15_Deque_iteratorIyRyPyES4_
	.section	.text._ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb,"axG",@progbits,_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb,comdat
	.align 2
	.weak	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	.type	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb, @function
_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb:
.LFB5024:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	movl	%edx, %ecx
	movq	%rsi, %r15
	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
	movq	%rdi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 56
	.cfi_offset 3, -56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	movq	72(%rdi), %rdx
	movq	40(%rdi), %rsi
	movq	%rdx, %r12
	subq	%rsi, %r12
	movq	%r12, %rax
	sarq	$3, %rax
	leaq	1(%r15,%rax), %r8
	movq	8(%rdi), %rax
	leaq	(%r8,%r8), %rdi
	cmpq	%rax, %rdi
	jnb	.L53
	subq	%r8, %rax
	movq	0(%rbp), %rbx
	xorl	%edi, %edi
	shrq	%rax
	salq	$3, %rax
	testb	%cl, %cl
	je	.L54
	leaq	0(,%r15,8), %rdi
.L54:
	addq	%rdi, %rax
	addq	$8, %rdx
	addq	%rax, %rbx
	subq	%rsi, %rdx
	cmpq	%rsi, %rbx
	jnb	.L55
	movq	%rbx, %rdi
	cmpq	$8, %rdx
	jg	.L69
	jne	.L59
	movq	(%rsi), %rax
	movq	%rax, (%rbx)
	jmp	.L59
.L55:
	leaq	8(%rbx,%r12), %rdi
	cmpq	$8, %rdx
	jle	.L60
	subq	%rdx, %rdi
.L69:
	call	memmove@PLT
	jmp	.L59
.L60:
	jne	.L59
	movq	(%rsi), %rax
	movq	%rax, -8(%rdi)
	jmp	.L59
.L53:
	cmpq	%r15, %rax
	movq	%r15, %rdx
	cmovnb	%rax, %rdx
	leaq	2(%rax,%rdx), %r13
	movabsq	$1152921504606846975, %rax
	cmpq	%r13, %rax
	jnb	.L61
	movabsq	$2305843009213693951, %rax
	cmpq	%r13, %rax
	jnb	.L62
	call	_ZSt28__throw_bad_array_new_lengthv@PLT
.L62:
	call	_ZSt17__throw_bad_allocv@PLT
.L61:
	leaq	0(,%r13,8), %rdi
	movl	%ecx, 12(%rsp)
	movq	%r13, %rbx
	movq	%r8, (%rsp)
	call	_Znwm@PLT
	movq	(%rsp), %r8
	movl	12(%rsp), %ecx
	movq	%rax, %r14
	xorl	%eax, %eax
	subq	%r8, %rbx
	shrq	%rbx
	salq	$3, %rbx
	testb	%cl, %cl
	je	.L63
	leaq	0(,%r15,8), %rax
.L63:
	addq	%rax, %rbx
	movq	72(%rbp), %rax
	movq	40(%rbp), %rsi
	addq	%r14, %rbx
	leaq	8(%rax), %rdx
	subq	%rsi, %rdx
	cmpq	$8, %rdx
	jle	.L64
	movq	%rbx, %rdi
	call	memmove@PLT
	jmp	.L65
.L64:
	jne	.L65
	movq	(%rsi), %rax
	movq	%rax, (%rbx)
.L65:
	movq	8(%rbp), %rax
	movq	0(%rbp), %rdi
	leaq	0(,%rax,8), %rsi
	call	_ZdlPvm@PLT
	movq	%r14, 0(%rbp)
	movq	%r13, 8(%rbp)
.L59:
	movq	(%rbx), %rax
	movq	%rbx, 40(%rbp)
	addq	%r12, %rbx
	movq	%rbx, 72(%rbp)
	movq	%rax, 24(%rbp)
	addq	$512, %rax
	movq	%rax, 32(%rbp)
	movq	(%rbx), %rax
	movq	%rax, 56(%rbp)
	addq	$512, %rax
	movq	%rax, 64(%rbp)
	addq	$24, %rsp
	.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
	.cfi_endproc
.LFE5024:
	.size	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb, .-_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	.section	.text._ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm,"axG",@progbits,_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm,comdat
	.align 2
	.weak	_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm
	.type	_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm, @function
_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm:
.LFB4979:
	.cfi_startproc
	endbr64
	movq	72(%rdi), %rax
	movq	8(%rdi), %rdx
	leaq	1(%rsi), %rcx
	subq	(%rdi), %rax
	sarq	$3, %rax
	subq	%rax, %rdx
	cmpq	%rcx, %rdx
	jnb	.L70
	xorl	%edx, %edx
	jmp	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
.L70:
	ret
	.cfi_endproc
.LFE4979:
	.size	_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm, .-_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm
	.section	.rodata._ZNSt5dequeIySaIyEE9push_backERKy.str1.1,"aMS",@progbits,1
.LC1:
	.string	"cannot create std::deque larger than max_size()"
	.section	.text._ZNSt5dequeIySaIyEE9push_backERKy,"axG",@progbits,_ZNSt5dequeIySaIyEE9push_backERKy,comdat
	.align 2
	.weak	_ZNSt5dequeIySaIyEE9push_backERKy
	.type	_ZNSt5dequeIySaIyEE9push_backERKy, @function
_ZNSt5dequeIySaIyEE9push_backERKy:
.LFB4780:
	.cfi_startproc
	endbr64
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rsi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	64(%rdi), %rcx
	movq	%rdi, %rbx
	movq	48(%rdi), %rax
	leaq	-8(%rcx), %rdx
	cmpq	%rdx, %rax
	je	.L73
	movq	(%rsi), %rdx
	addq	$8, %rax
	movq	%rdx, -8(%rax)
	jmp	.L74
.L73:
	leaq	16(%rdi), %rsi
	leaq	48(%rdi), %rdi
	call	_ZStmiRKSt15_Deque_iteratorIyRyPyES4_
	movq	%rax, %rdx
	movabsq	$1152921504606846975, %rax
	cmpq	%rax, %rdx
	jne	.L75
	leaq	.LC1(%rip), %rdi
	call	_ZSt20__throw_length_errorPKc@PLT
.L75:
	movl	$1, %esi
	movq	%rbx, %rdi
	call	_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm
	movq	72(%rbx), %r12
	movl	$512, %edi
	call	_Znwm@PLT
	movq	0(%rbp), %rdx
	movq	%rax, 8(%r12)
	movq	48(%rbx), %rax
	movq	%rdx, (%rax)
	movq	72(%rbx), %rax
	leaq	8(%rax), %rdx
	movq	8(%rax), %rax
	movq	%rdx, 72(%rbx)
	leaq	512(%rax), %rdx
	movq	%rax, 56(%rbx)
	movq	%rdx, 64(%rbx)
.L74:
	movq	%rax, 48(%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE4780:
	.size	_ZNSt5dequeIySaIyEE9push_backERKy, .-_ZNSt5dequeIySaIyEE9push_backERKy
	.text
	.align 2
	.type	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0, @function
_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0:
.LFB5087:
	.cfi_startproc
	pushq	%r12
	.cfi_def_cfa_offset 16
	.cfi_offset 12, -16
	pushq	%rbp
	.cfi_def_cfa_offset 24
	.cfi_offset 6, -24
	movq	%rsi, %rbp
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset 3, -32
	movq	64(%rdi), %rcx
	movq	%rdi, %rbx
	movq	48(%rdi), %rax
	leaq	-8(%rcx), %rdx
	cmpq	%rdx, %rax
	je	.L78
	movq	(%rsi), %rdx
	addq	$8, %rax
	movq	%rdx, -8(%rax)
	jmp	.L79
.L78:
	leaq	16(%rdi), %rsi
	leaq	48(%rdi), %rdi
	call	_ZStmiRKSt15_Deque_iteratorIyRyPyES4_
	movq	%rax, %rdx
	movabsq	$1152921504606846975, %rax
	cmpq	%rax, %rdx
	jne	.L80
	leaq	.LC1(%rip), %rdi
	call	_ZSt20__throw_length_errorPKc@PLT
.L80:
	movl	$1, %esi
	movq	%rbx, %rdi
	call	_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm
	movq	72(%rbx), %r12
	movl	$512, %edi
	call	_Znwm@PLT
	movq	0(%rbp), %rdx
	movq	%rax, 8(%r12)
	movq	48(%rbx), %rax
	movq	%rdx, (%rax)
	movq	72(%rbx), %rax
	leaq	8(%rax), %rdx
	movq	8(%rax), %rax
	movq	%rdx, 72(%rbx)
	leaq	512(%rax), %rdx
	movq	%rax, 56(%rbx)
	movq	%rdx, 64(%rbx)
.L79:
	movq	%rax, 48(%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%rbp
	.cfi_def_cfa_offset 16
	popq	%r12
	.cfi_def_cfa_offset 8
	ret
	.cfi_endproc
.LFE5087:
	.size	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0, .-_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0
	.globl	_Z13iterative_bfsPPsysPPb
	.type	_Z13iterative_bfsPPsysPPb, @function
_Z13iterative_bfsPPsysPPb:
.LFB4262:
	.cfi_startproc
	.cfi_personality 0x9b,DW.ref.__gxx_personality_v0
	.cfi_lsda 0x1b,.LLSDA4262
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	movl	%edx, %r14d
	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	$248, %rsp
	.cfi_def_cfa_offset 304
	movq	%fs:40, %rax
	movq	%rax, 232(%rsp)
	movq	(%rdi), %rax
	cmpw	%dx, (%rax)
	je	.L83
	movq	(%rcx), %rax
	movq	%rdi, %r12
	movq	%rsi, %r13
	movq	%rcx, %rbp
	movb	$1, (%rax)
	leaq	72(%rsp), %rax
	movq	%rax, %rdi
	movq	%rax, 8(%rsp)
.LEHB5:
	call	_ZNSt5queueIySt5dequeIySaIyEEEC1IS2_vEEv
.LEHE5:
	leaq	152(%rsp), %rax
	movq	%rax, %rdi
	movq	%rax, 16(%rsp)
.LEHB6:
	call	_ZNSt5queueIySt5dequeIySaIyEEEC1IS2_vEEv
.LEHE6:
	leaq	64(%rsp), %rax
	movq	8(%rsp), %rdi
	xorl	%edx, %edx
	movq	%rax, %rsi
	movq	%rdx, 64(%rsp)
	movq	%rax, 24(%rsp)
.LEHB7:
	call	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0
	movq	24(%rsp), %rsi
	movq	16(%rsp), %rdi
	xorl	%eax, %eax
	movq	%rax, 64(%rsp)
	call	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0
	leaq	56(%rsp), %rax
	movq	%rax, 40(%rsp)
.L84:
	movq	88(%rsp), %rax
	cmpq	%rax, 120(%rsp)
	je	.L100
	movq	168(%rsp), %rdx
	movq	(%rax), %rax
	movq	8(%rsp), %rdi
	movq	(%rdx), %rbx
	movq	%rax, 48(%rsp)
	movq	%rax, 32(%rsp)
	movq	%rbx, 56(%rsp)
	call	_ZNSt5dequeIySaIyEE9pop_frontEv
	movq	16(%rsp), %rdi
	call	_ZNSt5dequeIySaIyEE9pop_frontEv
	movq	32(%rsp), %rax
	leaq	0(,%rax,8), %rdx
	leaq	0(%rbp,%rdx), %r15
	movq	(%r15), %rcx
	movb	$1, (%rcx,%rbx)
	movq	(%r12,%rax,8), %rcx
	cmpw	%r14w, (%rcx,%rbx,2)
	je	.L86
	incq	%rax
	cmpq	%r13, %rax
	jb	.L87
.L90:
	leaq	1(%rbx), %rax
	movq	%rax, 32(%rsp)
	cmpq	%r13, %rax
	jb	.L88
	jmp	.L84
.L87:
	movq	8(%rbp,%rdx), %rdx
	cmpb	$0, (%rdx,%rbx)
	jne	.L90
	movq	24(%rsp), %rsi
	movq	8(%rsp), %rdi
	movq	%rax, 64(%rsp)
	call	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0
	movq	40(%rsp), %rsi
	movq	16(%rsp), %rdi
	call	_ZNSt5dequeIySaIyEE9push_backERKy
	jmp	.L90
.L88:
	movq	(%r15), %rax
	cmpb	$0, 1(%rax,%rbx)
	jne	.L84
	movq	8(%rsp), %rdi
	leaq	48(%rsp), %rsi
	call	_ZNSt5dequeIySaIyEE9push_backERKy
	movq	32(%rsp), %rax
	movq	24(%rsp), %rsi
	movq	16(%rsp), %rdi
	movq	%rax, 64(%rsp)
	call	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_.isra.0
.LEHE7:
	jmp	.L84
.L100:
	orl	$-1, %r14d
.L86:
	movq	16(%rsp), %rdi
	call	_ZNSt11_Deque_baseIySaIyEED2Ev
	movq	8(%rsp), %rdi
	call	_ZNSt11_Deque_baseIySaIyEED2Ev
.L83:
	movq	232(%rsp), %rax
	subq	%fs:40, %rax
	je	.L95
	jmp	.L98
.L97:
	endbr64
	movq	%rax, %rbx
.L92:
	movq	16(%rsp), %rdi
	call	_ZNSt11_Deque_baseIySaIyEED2Ev
	jmp	.L93
.L96:
	endbr64
	movq	%rax, %rbx
.L93:
	movq	8(%rsp), %rdi
	call	_ZNSt11_Deque_baseIySaIyEED2Ev
	movq	232(%rsp), %rax
	subq	%fs:40, %rax
	jne	.L98
	movq	%rbx, %rdi
.LEHB8:
	call	_Unwind_Resume@PLT
.LEHE8:
.L98:
	call	__stack_chk_fail@PLT
.L95:
	addq	$248, %rsp
	.cfi_def_cfa_offset 56
	movl	%r14d, %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
.LFE4262:
	.section	.gcc_except_table,"a",@progbits
.LLSDA4262:
	.byte	0xff
	.byte	0xff
	.byte	0x1
	.uleb128 .LLSDACSE4262-.LLSDACSB4262
.LLSDACSB4262:
	.uleb128 .LEHB5-.LFB4262
	.uleb128 .LEHE5-.LEHB5
	.uleb128 0
	.uleb128 0
	.uleb128 .LEHB6-.LFB4262
	.uleb128 .LEHE6-.LEHB6
	.uleb128 .L96-.LFB4262
	.uleb128 0
	.uleb128 .LEHB7-.LFB4262
	.uleb128 .LEHE7-.LEHB7
	.uleb128 .L97-.LFB4262
	.uleb128 0
	.uleb128 .LEHB8-.LFB4262
	.uleb128 .LEHE8-.LEHB8
	.uleb128 0
	.uleb128 0
.LLSDACSE4262:
	.text
	.size	_Z13iterative_bfsPPsysPPb, .-_Z13iterative_bfsPPsysPPb
	.section	.rodata.str1.1
.LC2:
	.string	"Enter N (NxN matrix): "
.LC3:
	.string	"Enter target integer [0 to 100]: "
.LC4:
	.string	"----------------------------------------------------------"
.LC5:
	.string	"Found: "
.LC6:
	.string	"[CUDA] Elapsed time: "
.LC7:
	.string	" clock cycles"
.LC8:
	.string	"Starting sequential iterative approach."
.LC11:
	.string	"[SEQUENTIAL - Iterative] Elapsed time: "
.LC12:
	.string	"Starting sequential recursive approach."
.LC13:
	.string	"[SEQUENTIAL - Recursive] Elapsed time: "
	.section	.text.startup
	.globl	main
	.type	main, @function
main:
.LFB4261:
	.cfi_startproc
	endbr64
	pushq	%r15
	.cfi_def_cfa_offset 16
	.cfi_offset 15, -16
	leaq	.LC2(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	pushq	%r14
	.cfi_def_cfa_offset 24
	.cfi_offset 14, -24
	xorl	%r14d, %r14d
	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
	leaq	_ZSt3cin(%rip), %rbx
	subq	$88, %rsp
	.cfi_def_cfa_offset 144
	movq	%fs:40, %rax
	movq	%rax, 72(%rsp)
	xorl	%eax, %eax
	movq	$100, 24(%rsp)
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	%rbx, %rdi
	leaq	24(%rsp), %rsi
	call	_ZNSi10_M_extractIyEERSiRT_@PLT
	leaq	.LC3(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	leaq	18(%rsp), %rsi
	movq	%rbx, %rdi
	call	_ZNSirsERs@PLT
	movq	24(%rsp), %r12
	leaq	0(,%r12,8), %rbx
	movq	%rbx, %rdi
	imulq	%r12, %r12
	call	malloc@PLT
	movq	%rbx, %rdi
	movq	%rax, %rbp
	call	malloc@PLT
	movl	$2, %edi
	movq	%rax, %rbx
	call	malloc@PLT
	movl	$4, %edi
	movq	%rax, %r15
	call	malloc@PLT
	leaq	(%r12,%r12), %rdi
	movq	%rax, %r13
	call	malloc@PLT
	xorl	%edi, %edi
	movq	%rax, %r12
	call	time@PLT
	movl	%eax, %edi
	call	srand@PLT
.L102:
	movq	24(%rsp), %rsi
	cmpq	%rsi, %r14
	jnb	.L114
	leaq	(%rsi,%rsi), %rdi
	movq	%rsi, 8(%rsp)
	call	malloc@PLT
	movq	8(%rsp), %rdi
	movq	%rax, 0(%rbp,%r14,8)
	call	malloc@PLT
	xorl	%esi, %esi
	movq	%rax, (%rbx,%r14,8)
.L103:
	cmpq	24(%rsp), %rsi
	jnb	.L115
	movq	%rsi, 8(%rsp)
	call	rand@PLT
	movl	$101, %ecx
	movq	8(%rsp), %rsi
	cltd
	idivl	%ecx
	movq	0(%rbp,%r14,8), %rax
	movw	%dx, (%rax,%rsi,2)
	movq	(%rbx,%r14,8), %rax
	movb	$0, (%rax,%rsi)
	movq	24(%rsp), %rax
	imulq	%r14, %rax
	addq	%rsi, %rax
	incq	%rsi
	movw	%dx, (%r12,%rax,2)
	jmp	.L103
.L115:
	incq	%r14
	jmp	.L102
.L114:
	imulq	%rsi, %rsi
	leaq	40(%rsp), %rdi
	addq	%rsi, %rsi
	call	cudaMalloc@PLT
	leaq	32(%rsp), %rdi
	movl	$4, %esi
	call	cudaMalloc@PLT
	leaq	48(%rsp), %rdi
	movl	$4, %esi
	call	cudaMalloc@PLT
	movq	32(%rsp), %rdi
	xorl	%esi, %esi
	movl	$4, %edx
	call	cudaMemset@PLT
	movq	48(%rsp), %rdi
	xorl	%esi, %esi
	movl	$2, %edx
	call	cudaMemset@PLT
	leaq	56(%rsp), %rdi
	call	cudaEventCreate@PLT
	leaq	64(%rsp), %rdi
	call	cudaEventCreate@PLT
	movq	24(%rsp), %rdx
	movq	40(%rsp), %rdi
	movq	%r12, %rsi
	movl	$1, %ecx
	imulq	%rdx, %rdx
	addq	%rdx, %rdx
	call	cudaMemcpy@PLT
	movq	56(%rsp), %rdi
	xorl	%esi, %esi
	call	cudaEventRecord@PLT
	movswl	18(%rsp), %r8d
	movq	24(%rsp), %rcx
	movq	48(%rsp), %rdx
	movq	32(%rsp), %rsi
	movq	40(%rsp), %rdi
	call	_Z18kernel_bfs_wrapperPsPiS0_ys
	movq	64(%rsp), %rdi
	xorl	%esi, %esi
	call	cudaEventRecord@PLT
	movq	64(%rsp), %rdi
	call	cudaEventSynchronize@PLT
	movq	64(%rsp), %rdx
	movq	56(%rsp), %rsi
	leaq	20(%rsp), %rdi
	call	cudaEventElapsedTime@PLT
	movq	32(%rsp), %rsi
	movl	$4, %edx
	movq	%r13, %rdi
	movl	$2, %ecx
	call	cudaMemcpy@PLT
	movq	56(%rsp), %rdi
	call	cudaEventDestroy@PLT
	movq	64(%rsp), %rdi
	call	cudaEventDestroy@PLT
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC5(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	%rax, %rdi
	movslq	0(%r13), %rax
	movswl	(%r12,%rax,2), %esi
	call	_ZNSolsEs@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC6(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	cvtss2sd	20(%rsp), %xmm0
	movq	%rax, %rdi
	call	_ZNSo9_M_insertIdEERSoT_@PLT
	leaq	.LC7(%rip), %rsi
	movq	%rax, %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC8(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	movq	24(%rsp), %rsi
	xorl	%edx, %edx
	xorl	%eax, %eax
.L106:
	cmpq	%rdx, %rsi
	je	.L116
	movq	(%rbx,%rdx,8), %rdi
	movq	%rsi, %rcx
	incq	%rdx
	rep stosb
	jmp	.L106
.L116:
	call	clock@PLT
	movswl	18(%rsp), %edx
	movq	%rbx, %rcx
	movq	%rbp, %rdi
	cvtsi2sdq	%rax, %xmm1
	movq	24(%rsp), %rsi
	movsd	%xmm1, 8(%rsp)
	call	_Z13iterative_bfsPPsysPPb
	movl	%eax, %r14d
	call	clock@PLT
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	cvtsi2sdq	%rax, %xmm0
	subsd	8(%rsp), %xmm0
	mulsd	.LC9(%rip), %xmm0
	divsd	.LC10(%rip), %xmm0
	movsd	%xmm0, 8(%rsp)
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC5(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movswl	%r14w, %esi
	movq	%rax, %rdi
	call	_ZNSolsEs@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC11(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movsd	8(%rsp), %xmm0
	movq	%rax, %rdi
	call	_ZNSo9_M_insertIdEERSoT_@PLT
	leaq	.LC7(%rip), %rsi
	movq	%rax, %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC12(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	movq	24(%rsp), %rsi
	xorl	%edx, %edx
	xorl	%eax, %eax
.L108:
	cmpq	%rdx, %rsi
	je	.L117
	movq	(%rbx,%rdx,8), %rdi
	movq	%rsi, %rcx
	incq	%rdx
	rep stosb
	jmp	.L108
.L117:
	call	clock@PLT
	movswl	18(%rsp), %edx
	movq	%rbx, %rcx
	movq	%rbp, %rdi
	cvtsi2sdq	%rax, %xmm3
	movq	24(%rsp), %rsi
	movsd	%xmm3, 8(%rsp)
	call	_Z13recursive_bfsPPsysPPb
	movw	%ax, (%r15)
	movl	%eax, %r14d
	call	clock@PLT
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	cvtsi2sdq	%rax, %xmm0
	subsd	8(%rsp), %xmm0
	mulsd	.LC9(%rip), %xmm0
	divsd	.LC10(%rip), %xmm0
	movsd	%xmm0, 8(%rsp)
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC5(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movswl	%r14w, %esi
	xorl	%r14d, %r14d
	movq	%rax, %rdi
	call	_ZNSolsEs@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC13(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movsd	8(%rsp), %xmm0
	movq	%rax, %rdi
	call	_ZNSo9_M_insertIdEERSoT_@PLT
	leaq	.LC7(%rip), %rsi
	movq	%rax, %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
	leaq	.LC4(%rip), %rsi
	leaq	_ZSt4cout(%rip), %rdi
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc@PLT
	movq	_ZSt4endlIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_@GOTPCREL(%rip), %rsi
	movq	%rax, %rdi
	call	_ZNSolsEPFRSoS_E.isra.0
.L110:
	cmpq	24(%rsp), %r14
	jnb	.L118
	movq	0(%rbp,%r14,8), %rdi
	call	free@PLT
	movq	(%rbx,%r14,8), %rdi
	incq	%r14
	call	free@PLT
	jmp	.L110
.L118:
	movq	%rbp, %rdi
	call	free@PLT
	movq	%rbx, %rdi
	call	free@PLT
	movq	%r12, %rdi
	call	free@PLT
	movq	%r15, %rdi
	call	free@PLT
	movq	%r13, %rdi
	call	free@PLT
	movq	40(%rsp), %rdi
	call	cudaFree@PLT
	movq	48(%rsp), %rdi
	call	cudaFree@PLT
	movq	32(%rsp), %rdi
	call	cudaFree@PLT
	movq	72(%rsp), %rax
	subq	%fs:40, %rax
	je	.L112
	call	__stack_chk_fail@PLT
.L112:
	addq	$88, %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
	ret
	.cfi_endproc
.LFE4261:
	.size	main, .-main
	.section	.nvFatBinSegment,"aw"
	.align 8
	.type	_ZL15__fatDeviceText, @object
	.size	_ZL15__fatDeviceText, 24
_ZL15__fatDeviceText:
	.long	1180844977
	.long	1
	.quad	fatbinData
	.quad	0
	.local	_ZL20__cudaFatCubinHandle
	.comm	_ZL20__cudaFatCubinHandle,8,8
	.section	.rodata.cst8,"aM",@progbits,8
	.align 8
.LC9:
	.long	0
	.long	1083129856
	.align 8
.LC10:
	.long	0
	.long	1093567616
	.hidden	DW.ref.__gxx_personality_v0
	.weak	DW.ref.__gxx_personality_v0
	.section	.data.rel.local.DW.ref.__gxx_personality_v0,"awG",@progbits,DW.ref.__gxx_personality_v0,comdat
	.align 8
	.type	DW.ref.__gxx_personality_v0, @object
	.size	DW.ref.__gxx_personality_v0, 8
DW.ref.__gxx_personality_v0:
	.quad	__gxx_personality_v0
	.ident	"GCC: (Ubuntu 13.3.0-6ubuntu2~24.04) 13.3.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 <hip/hip_runtime.h>
#include <iostream>
#include <cstdlib>
#include <stdlib.h>
#include <ctime>
#include <queue>

using namespace std;

short iterative_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix);
short recursive_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix);
short recursive_bfs_helper(short **matrix, unsigned long long N, short target, unsigned long long x, unsigned long long y, bool **visited_matrix);

void kernel_bfs_wrapper(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target);
__global__ void bfs_kernel(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target);

int main()
{
  // default size is 100
  unsigned long long N = 100;
  int *h_found_idx, *found_idx;
  short **seq_matrix,
  *h_matrix,
  *cuda_matrix,
  *seq_result,
  *cuda_result,
  target;
  int *mtx;
  bool **visited_matrix;

  // Declare timers
  float cuda_elapsed_time;
  hipEvent_t cuda_start, cuda_stop;
  double seq_start, seq_stop, seq_iter_elapsed_time, seq_recur_elapsed_time;

  cout << "Enter N (NxN matrix): ";
  cin >> N;

  cout << "Enter target integer [0 to 100]: ";
  cin >> target;

  // allocate memory for seq
  seq_matrix = (short**) malloc(N * sizeof(short*));
  visited_matrix = (bool**) malloc(N * sizeof(bool*));
  seq_result = (short*) malloc(sizeof(short));
  h_found_idx = (int*) malloc(sizeof(int));
  h_matrix = (short*) malloc(N * N * sizeof(short));
  srand(time(0));
  // set matrix to random shortegers from 0 to 100
  for (unsigned long long i = 0; i < N; i++) {
    seq_matrix[i] = (short*) malloc(N * sizeof(short));
    visited_matrix[i] = (bool*) malloc(N * sizeof(bool));
    for (unsigned long long j = 0; j < N; j++) {
      seq_matrix[i][j] = rand() % 101;
      visited_matrix[i][j] = false;
      h_matrix[i*N + j] = seq_matrix[i][j];
    }
  }
  //cout << "random numbers generated" << endl;

  // allocate memory for cuda
  hipMalloc((void **) &cuda_matrix, N * N * sizeof(short));
  //cudaMallocPitch((void**)&cuda_matrix, &pitch, N * sizeof(short), N);
  //cudaMallocPitch((void**)&cuda_visited_matrix, &pitch_visited, N * sizeof(short), N);
  //for (unsigned long long i = 0; i < N; i++) {
  //  cudaMalloc(&cuda_matrix[i], N * sizeof(short));
  //}
  hipMalloc((void**)&found_idx, sizeof(int));
  //cudaMalloc((void**)&cuda_result, sizeof(short));
  hipMalloc((void**)&mtx, sizeof(int));
  //cout << "cuda malloc good" << endl;

  // set values of cuda target to -1 (not found)
  // set values of mtx target to 0
  hipMemset(found_idx, 0, sizeof(int));
  //cudaMemset(cuda_result, -1, sizeof(short));
  hipMemset(mtx, 0, sizeof(short));

  // set up timing variables
  hipEventCreate(&cuda_start);
  hipEventCreate(&cuda_stop);
  //for (unsigned long long i = 0; i < N; i++) {
  //  cudaMemcpy(cuda_matrix[i], seq_matrix[i], N * sizeof(short), cudaMemcpyHostToDevice);
    //cudaMemcpy(cuda_visited_matrix[i], visited_matrix[i], N * sizeof(bool), cudaMemcpyHostToDevice);
  //}
  hipMemcpy(cuda_matrix, h_matrix, N * N * sizeof(short), hipMemcpyHostToDevice);
  //cudaMemcpy2DToArray(cuda_matrix, pitch, seq_matrix, N*sizeof(short), N*sizeof(short), N, cudaMemcpyHostToDevice);
  //cudaMemcpy2DToArray(cuda_visited_matrix, pitch_visited, visited_matrix, N*sizeof(bool), N*sizeof(bool), N, cudaMemcpyHostToDevice);
  //cudaMemcpy(cuda_matrix, seq_matrix, N * sizeof(short*), cudaMemcpyHostToDevice);
  //cudaMemcpy(cuda_visited_matrix, visited_matrix, N * sizeof(bool*), cudaMemcpyHostToDevice);
  // copy from host to device
  hipEventRecord(cuda_start, 0);

  // START CUDA
  kernel_bfs_wrapper(cuda_matrix, found_idx, mtx, N, target);

  // copy from device to host
  hipEventRecord(cuda_stop, 0);
  hipEventSynchronize(cuda_stop);
  hipEventElapsedTime(&cuda_elapsed_time, cuda_start, cuda_stop);
  //cudaMemcpy2D(seq_result, sizeof(short)*N, cuda_result, pitch, sizeof(short)*N, N, cudaMemcpyDeviceToHost);
  //cudaMemcpy(seq_result, cuda_result, sizeof(short), cudaMemcpyDeviceToHost);
  hipMemcpy(h_found_idx, found_idx, sizeof(int), hipMemcpyDeviceToHost);

  // destroy timers
  hipEventDestroy(cuda_start);
  hipEventDestroy(cuda_stop);

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << h_matrix[*h_found_idx] << endl;
  cout << "[CUDA] Elapsed time: " << cuda_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  cout << endl;

  cout << "Starting sequential iterative approach." << endl;

  // reset visited_matrix back to false
  for (unsigned long long i = 0; i < N; i++) {
    for (unsigned long long j = 0; j < N; j++) {
      visited_matrix[i][j] = false;
    }
  }

  seq_start = (double) clock();

  // call iterative bfs
  *seq_result = -1;
  *seq_result = iterative_bfs(seq_matrix, N, target, visited_matrix);

  seq_stop = (double) clock();
  seq_iter_elapsed_time = (double) 1000.0*((double)(seq_stop - seq_start))/CLOCKS_PER_SEC;

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << *seq_result << endl;
  cout << "[SEQUENTIAL - Iterative] Elapsed time: " << seq_iter_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  cout << "Starting sequential recursive approach." << endl;

  // reset visited_matrix back to false
  for (unsigned long long i = 0; i < N; i++) {
    for (unsigned long long j = 0; j < N; j++) {
      visited_matrix[i][j] = false;
    }
  }

  seq_start = (double) clock();

  // call recursive bfs
  *seq_result = -1;
  *seq_result = recursive_bfs(seq_matrix, N, target, visited_matrix);

  seq_stop = (double) clock();
  seq_recur_elapsed_time = (double) 1000.0*((double)(seq_stop - seq_start))/CLOCKS_PER_SEC;

  cout << "----------------------------------------------------------" << endl;
  cout << "Found: " << *seq_result << endl;
  cout << "[SEQUENTIAL - Recursive] Elapsed time: " << seq_recur_elapsed_time << " clock cycles" << endl;
  cout << "----------------------------------------------------------" << endl;

  // free and cuda free
  for (unsigned long long i = 0; i < N; i++) {
    free(seq_matrix[i]);
    free(visited_matrix[i]);
  }
  free(seq_matrix);
  free(visited_matrix);
  free(h_matrix);
  free(seq_result);
  free(h_found_idx);
  hipFree(cuda_matrix);
  hipFree(mtx);
  hipFree(found_idx);
  //cudaFree(cuda_result);

  return 0;
}

short iterative_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix) {
  // check initial spot
  if (matrix[0][0] == target)
    return matrix[0][0];

  visited_matrix[0][0] = true;
  queue<unsigned long long> qx;
  queue<unsigned long long> qy;
  qx.push(0);
  qy.push(0);
  while (!qx.empty()) {
    unsigned long long x = qx.front();
    unsigned long long y = qy.front();
    qx.pop();
    qy.pop();
    visited_matrix[x][y] = true;
    if (matrix[x][y] == target) {
      return matrix[x][y];
    }
    // check right then check down
    if (x + 1 < N && !visited_matrix[x+1][y]) {
      qx.push(x+1);
      qy.push(y);
    }
    if (y + 1 < N && !visited_matrix[x][y+1]) {
      qx.push(x);
      qy.push(y+1);
    }
  }
  return -1;
}

short recursive_bfs(short **matrix, unsigned long long N, short target, bool **visited_matrix) {
  // check initial spot
  if (matrix[0][0] == target)
    return matrix[0][0];

  visited_matrix[0][0] = true;

  return recursive_bfs_helper(matrix, N, target, 0, 0, visited_matrix);
}

short recursive_bfs_helper(short **matrix, unsigned long long N, short target, unsigned long long x, unsigned long long y, bool **visited_matrix) {
  // check right
  if (x+1 < N && matrix[x+1][y] == target)
    return matrix[x+1][y];
  // check down
  if (y+1 < N && matrix[x][y+1] == target)
    return matrix[x][y+1];

  // traverse to right first, then down
  short right = -1;
  short down = -1;

  if (x+1 < N && !visited_matrix[x+1][y]) {
    visited_matrix[x+1][y] = true;
    right = recursive_bfs_helper(matrix, N, target, x+1, y, visited_matrix);
  }
  // if found in right, then return right
  if (right != -1)
    return right;

  if (y+1 < N && !visited_matrix[x][y+1]) {
    visited_matrix[x][y+1] = true;
    down = recursive_bfs_helper(matrix, N, target, x, y+1, visited_matrix);
  }
  // if found in down, then return down
  if (down != -1)
    return down;

  // otherwise, nothing has been found.
  return -1;
}

void kernel_bfs_wrapper(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target)
{
  // 1 dimensional
  dim3 blockSize = (256);
  dim3 gridSize = ((N*N + (2048 - 1))/(2048));
  bfs_kernel<<< gridSize, blockSize >>>(matrix, found_idx, mtx, N, target);
}

__global__ void bfs_kernel(short *matrix, int *found_idx, int *mtx, unsigned long long N, short target)
{
  int idx = threadIdx.x + blockDim.x * blockIdx.x;
  //unsigned long long idy = threadIdx.y + blockDim.y + blockIdx.y; 

  if (idx >= N*N) {
    return;
  }
  //printf("%d\n", matrix[idx]);
  //short *row = (short*) ((char*) matrix + ;
  // found!!
  if (matrix[idx] == target) {
    //printf("%d\n", matrix[idx]);
    //while(atomicCAS(mtx, 0, 1) != 0);
    //printf("Set\n");
    //*result = matrix[idx];
    atomicMax(found_idx, idx);
    //printf("found id: %d\n", *found_idx);
    //printf("id: %d\n", idx);
    //printf("Result: %d\n", *result);
    //atomicExch(mtx, 0);
    //printf("Keep going\n");
  }
}

	.text
	.file	"bfs.hip"
                                        # Start of file scope inline assembly
	.globl	_ZSt21ios_base_library_initv

                                        # End of file scope inline assembly
	.section	.rodata.cst8,"aM",@progbits,8
	.p2align	3, 0x0                          # -- Begin function main
.LCPI0_0:
	.quad	0x408f400000000000              # double 1000
.LCPI0_1:
	.quad	0x412e848000000000              # double 1.0E+6
	.text
	.globl	main
	.type	main,@function
main:                                   # @main
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$104, %rsp
	.cfi_def_cfa_offset 160
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	leaq	16(%rsp), %r14
	movq	$100, (%r14)
	movl	$_ZSt4cout, %edi
	movl	$.L.str, %esi
	movl	$22, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movl	$_ZSt3cin, %edi
	movq	%r14, %rsi
	callq	_ZNSi10_M_extractIyEERSiRT_
	movl	$_ZSt4cout, %edi
	movl	$.L.str.1, %esi
	movl	$33, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	leaq	6(%rsp), %rsi
	movl	$_ZSt3cin, %edi
	callq	_ZNSirsERs
	movq	(%r14), %r12
	leaq	(,%r12,8), %r15
	movq	%r15, %rdi
	callq	malloc
	movq	%rax, 40(%rsp)                  # 8-byte Spill
	movq	%r15, %rdi
	callq	malloc
	movq	%rax, 24(%rsp)                  # 8-byte Spill
	movl	$4, %edi
	callq	malloc
	movq	%rax, 48(%rsp)                  # 8-byte Spill
	imulq	%r12, %r12
	addq	%r12, %r12
	movq	%r12, %rdi
	callq	malloc
	movq	%rax, 32(%rsp)                  # 8-byte Spill
	xorl	%r13d, %r13d
	xorl	%edi, %edi
	callq	time
	movl	%eax, %edi
	callq	srand
	movq	(%r14), %rax
	testq	%rax, %rax
	je	.LBB0_5
# %bb.1:                                # %.lr.ph.preheader.preheader
	xorl	%ebx, %ebx
	movq	%rax, %r13
	xorl	%r15d, %r15d
.LBB0_2:                                # %.lr.ph.preheader
                                        # =>This Loop Header: Depth=1
                                        #     Child Loop BB0_3 Depth 2
	leaq	(,%r13,2), %rdi
	callq	malloc
	movq	%rax, %r14
	movq	40(%rsp), %rax                  # 8-byte Reload
	movq	%r14, (%rax,%r15,8)
	movq	%r13, %rdi
	callq	malloc
	movq	%rax, %rbp
	movq	24(%rsp), %rax                  # 8-byte Reload
	movq	%r15, 8(%rsp)                   # 8-byte Spill
	movq	%rbp, (%rax,%r15,8)
	xorl	%r12d, %r12d
	movq	32(%rsp), %r15                  # 8-byte Reload
.LBB0_3:                                # %.lr.ph
                                        #   Parent Loop BB0_2 Depth=1
                                        # =>  This Inner Loop Header: Depth=2
	callq	rand
	cltq
	imulq	$680390859, %rax, %rcx          # imm = 0x288DF0CB
	movq	%rcx, %rdx
	shrq	$63, %rdx
	shrq	$36, %rcx
	addl	%edx, %ecx
	imull	$101, %ecx, %ecx
	subl	%ecx, %eax
	movw	%ax, (%r14,%r12,2)
	movb	$0, (%rbp,%r12)
	movq	16(%rsp), %r13
	movq	%rbx, %rcx
	imulq	%r13, %rcx
	addq	%r15, %rcx
	movw	%ax, (%rcx,%r12,2)
	incq	%r12
	cmpq	%r13, %r12
	jb	.LBB0_3
# %bb.4:                                # %._crit_edge
                                        #   in Loop: Header=BB0_2 Depth=1
	movq	8(%rsp), %r15                   # 8-byte Reload
	incq	%r15
	addq	$2, %rbx
	cmpq	%r13, %r15
	jb	.LBB0_2
.LBB0_5:                                # %._crit_edge77
	imulq	%r13, %r13
	addq	%r13, %r13
	leaq	64(%rsp), %r12
	movq	%r12, %rdi
	movq	%r13, %rsi
	callq	hipMalloc
	leaq	72(%rsp), %r15
	movl	$4, %esi
	movq	%r15, %rdi
	callq	hipMalloc
	leaq	56(%rsp), %rbp
	movl	$4, %esi
	movq	%rbp, %rdi
	callq	hipMalloc
	movq	(%r15), %rdi
	movl	$4, %edx
	xorl	%esi, %esi
	callq	hipMemset
	movq	(%rbp), %rdi
	movl	$2, %edx
	xorl	%esi, %esi
	callq	hipMemset
	leaq	96(%rsp), %r14
	movq	%r14, %rdi
	callq	hipEventCreate
	leaq	88(%rsp), %r13
	movq	%r13, %rdi
	callq	hipEventCreate
	movq	(%r12), %rdi
	movq	16(%rsp), %rdx
	imulq	%rdx, %rdx
	addq	%rdx, %rdx
	movq	32(%rsp), %rbx                  # 8-byte Reload
	movq	%rbx, %rsi
	movl	$1, %ecx
	callq	hipMemcpy
	movq	(%r14), %rdi
	xorl	%esi, %esi
	callq	hipEventRecord
	movq	(%r12), %rdi
	movq	(%r15), %rsi
	movq	(%rbp), %rdx
	movq	16(%rsp), %rcx
	movswl	6(%rsp), %r8d
	callq	_Z18kernel_bfs_wrapperPsPiS0_ys
	movq	(%r13), %rdi
	xorl	%esi, %esi
	callq	hipEventRecord
	movq	(%r13), %rdi
	callq	hipEventSynchronize
	movq	(%r14), %rsi
	movq	(%r13), %rdx
	leaq	84(%rsp), %rbp
	movq	%rbp, %rdi
	callq	hipEventElapsedTime
	movq	(%r15), %rsi
	movl	$4, %edx
	movq	48(%rsp), %r12                  # 8-byte Reload
	movq	%r12, %rdi
	movl	$2, %ecx
	callq	hipMemcpy
	movq	(%r14), %rdi
	callq	hipEventDestroy
	movq	(%r13), %rdi
	callq	hipEventDestroy
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	movl	$_ZSt4cout, %r15d
	addq	%r15, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.3, %esi
	movl	$7, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movslq	(%r12), %rax
	movswl	(%rbx,%rax,2), %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSolsEs
	movq	%rax, %r14
	movq	(%rax), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.4, %esi
	movl	$21, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	cvtss2sd	(%rbp), %xmm0
	movl	$_ZSt4cout, %edi
	callq	_ZNSo9_M_insertIdEERSoT_
	movq	%rax, %r14
	movl	$.L.str.5, %esi
	movl	$13, %edx
	movq	%rax, %rdi
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	(%r14), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r15, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r15, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.6, %esi
	movl	$39, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r15, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movq	16(%rsp), %r14
	testq	%r14, %r14
	movq	24(%rsp), %r13                  # 8-byte Reload
	je	.LBB0_8
# %bb.6:                                # %.preheader72.preheader
	xorl	%ebx, %ebx
.LBB0_7:                                # %.preheader72
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r13,%rbx,8), %rdi
	xorl	%esi, %esi
	movq	%r14, %rdx
	callq	memset@PLT
	incq	%rbx
	cmpq	%rbx, %r14
	jne	.LBB0_7
.LBB0_8:                                # %._crit_edge80
	callq	clock
	xorps	%xmm0, %xmm0
	cvtsi2sd	%rax, %xmm0
	movsd	%xmm0, 8(%rsp)                  # 8-byte Spill
	movq	16(%rsp), %rsi
	movswl	6(%rsp), %edx
	movq	40(%rsp), %r15                  # 8-byte Reload
	movq	%r15, %rdi
	movq	%r13, %rcx
	callq	_Z13iterative_bfsPPsysPPb
	movl	%eax, %ebp
	callq	clock
	xorps	%xmm0, %xmm0
	cvtsi2sd	%rax, %xmm0
	subsd	8(%rsp), %xmm0                  # 8-byte Folded Reload
	mulsd	.LCPI0_0(%rip), %xmm0
	divsd	.LCPI0_1(%rip), %xmm0
	movsd	%xmm0, 8(%rsp)                  # 8-byte Spill
	movl	$_ZSt4cout, %r13d
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r13, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.3, %esi
	movl	$7, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movswl	%bp, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSolsEs
	movq	%rax, %r14
	movq	(%rax), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.7, %esi
	movl	$39, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movl	$_ZSt4cout, %edi
	movsd	8(%rsp), %xmm0                  # 8-byte Reload
                                        # xmm0 = mem[0],zero
	callq	_ZNSo9_M_insertIdEERSoT_
	movq	%rax, %r14
	movl	$.L.str.5, %esi
	movl	$13, %edx
	movq	%rax, %rdi
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	(%r14), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r13, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.8, %esi
	movl	$39, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r13, %rdi
	movq	24(%rsp), %r13                  # 8-byte Reload
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movq	16(%rsp), %r14
	testq	%r14, %r14
	je	.LBB0_11
# %bb.9:                                # %.preheader.preheader
	xorl	%ebx, %ebx
.LBB0_10:                               # %.preheader
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r13,%rbx,8), %rdi
	xorl	%esi, %esi
	movq	%r14, %rdx
	callq	memset@PLT
	incq	%rbx
	cmpq	%rbx, %r14
	jne	.LBB0_10
.LBB0_11:                               # %._crit_edge83
	callq	clock
	xorps	%xmm0, %xmm0
	cvtsi2sd	%rax, %xmm0
	movsd	%xmm0, 8(%rsp)                  # 8-byte Spill
	movzwl	6(%rsp), %ebp
	movq	(%r15), %rax
	cmpw	%bp, (%rax)
	je	.LBB0_13
# %bb.12:
	movq	16(%rsp), %rsi
	movq	(%r13), %rax
	movb	$1, (%rax)
	movswl	%bp, %edx
	movq	%r15, %rdi
	xorl	%ecx, %ecx
	xorl	%r8d, %r8d
	movq	%r13, %r9
	callq	_Z20recursive_bfs_helperPPsysyyPPb
	movl	%eax, %ebp
.LBB0_13:                               # %_Z13recursive_bfsPPsysPPb.exit
	callq	clock
	xorps	%xmm0, %xmm0
	cvtsi2sd	%rax, %xmm0
	subsd	8(%rsp), %xmm0                  # 8-byte Folded Reload
	mulsd	.LCPI0_0(%rip), %xmm0
	divsd	.LCPI0_1(%rip), %xmm0
	movsd	%xmm0, 8(%rsp)                  # 8-byte Spill
	movl	$_ZSt4cout, %r13d
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r13, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.3, %esi
	movl	$7, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movswl	%bp, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSolsEs
	movq	%rax, %r14
	movq	(%rax), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.9, %esi
	movl	$39, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movl	$_ZSt4cout, %edi
	movsd	8(%rsp), %xmm0                  # 8-byte Reload
                                        # xmm0 = mem[0],zero
	callq	_ZNSo9_M_insertIdEERSoT_
	movq	%rax, %r14
	movl	$.L.str.5, %esi
	movl	$13, %edx
	movq	%rax, %rdi
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	(%r14), %rax
	movq	-24(%rax), %rdi
	addq	%r14, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movq	%r14, %rdi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	movl	$_ZSt4cout, %edi
	movl	$.L.str.2, %esi
	movl	$58, %edx
	callq	_ZSt16__ostream_insertIcSt11char_traitsIcEERSt13basic_ostreamIT_T0_ES6_PKS3_l
	movq	_ZSt4cout(%rip), %rax
	movq	-24(%rax), %rdi
	addq	%r13, %rdi
	movl	$10, %esi
	callq	_ZNKSt9basic_iosIcSt11char_traitsIcEE5widenEc
	movsbl	%al, %esi
	movl	$_ZSt4cout, %edi
	callq	_ZNSo3putEc
	movq	%rax, %rdi
	callq	_ZNSo5flushEv
	cmpq	$0, 16(%rsp)
	movq	24(%rsp), %r14                  # 8-byte Reload
	je	.LBB0_16
# %bb.14:                               # %.lr.ph85.preheader
	xorl	%ebx, %ebx
.LBB0_15:                               # %.lr.ph85
                                        # =>This Inner Loop Header: Depth=1
	movq	(%r15,%rbx,8), %rdi
	callq	free
	movq	(%r14,%rbx,8), %rdi
	callq	free
	incq	%rbx
	cmpq	16(%rsp), %rbx
	jb	.LBB0_15
.LBB0_16:                               # %._crit_edge86
	movq	%r15, %rdi
	callq	free
	movq	%r14, %rdi
	callq	free
	movq	32(%rsp), %rdi                  # 8-byte Reload
	callq	free
	movq	%r12, %rdi
	callq	free
	movq	64(%rsp), %rdi
	callq	hipFree
	movq	56(%rsp), %rdi
	callq	hipFree
	movq	72(%rsp), %rdi
	callq	hipFree
	xorl	%eax, %eax
	addq	$104, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end0:
	.size	main, .Lfunc_end0-main
	.cfi_endproc
                                        # -- End function
	.globl	_Z18kernel_bfs_wrapperPsPiS0_ys # -- Begin function _Z18kernel_bfs_wrapperPsPiS0_ys
	.type	_Z18kernel_bfs_wrapperPsPiS0_ys,@function
_Z18kernel_bfs_wrapperPsPiS0_ys:        # @_Z18kernel_bfs_wrapperPsPiS0_ys
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r12
	.cfi_def_cfa_offset 40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -48
	.cfi_offset %r12, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%r8d, %ebp
	movq	%rcx, %rbx
	movq	%rdx, %r14
	movq	%rsi, %r15
	movq	%rdi, %r12
	movq	%rcx, %rax
	imulq	%rcx, %rax
	addq	$2047, %rax                     # imm = 0x7FF
	shrq	$11, %rax
	movl	%eax, %edi
	btsq	$32, %rdi
	movabsq	$4294967296, %rdx               # imm = 0x100000000
	orq	$256, %rdx                      # imm = 0x100
	movl	$1, %esi
	movl	$1, %ecx
	xorl	%r8d, %r8d
	xorl	%r9d, %r9d
	callq	__hipPushCallConfiguration
	testl	%eax, %eax
	je	.LBB1_2
# %bb.1:
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB1_2:
	.cfi_def_cfa_offset 48
	movswl	%bp, %r8d
	movq	%r12, %rdi
	movq	%r15, %rsi
	movq	%r14, %rdx
	movq	%rbx, %rcx
	popq	%rbx
	.cfi_def_cfa_offset 40
	popq	%r12
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	jmp	_Z25__device_stub__bfs_kernelPsPiS0_ys # TAILCALL
.Lfunc_end1:
	.size	_Z18kernel_bfs_wrapperPsPiS0_ys, .Lfunc_end1-_Z18kernel_bfs_wrapperPsPiS0_ys
	.cfi_endproc
                                        # -- End function
	.globl	_Z13iterative_bfsPPsysPPb       # -- Begin function _Z13iterative_bfsPPsysPPb
	.type	_Z13iterative_bfsPPsysPPb,@function
_Z13iterative_bfsPPsysPPb:              # @_Z13iterative_bfsPPsysPPb
.Lfunc_begin0:
	.cfi_startproc
	.cfi_personality 3, __gxx_personality_v0
	.cfi_lsda 3, .Lexception0
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$200, %rsp
	.cfi_def_cfa_offset 256
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%edx, %ebx
	movq	(%rdi), %rax
	cmpw	%bx, (%rax)
	je	.LBB2_32
# %bb.1:
	movq	%rcx, %r14
	movq	%rsi, %r15
	movq	%rdi, %r12
	movq	(%rcx), %rax
	movb	$1, (%rax)
	xorps	%xmm0, %xmm0
	leaq	32(%rsp), %rdi
	movaps	%xmm0, 64(%rdi)
	movaps	%xmm0, 48(%rdi)
	movaps	%xmm0, 32(%rdi)
	movaps	%xmm0, 16(%rdi)
	movaps	%xmm0, (%rdi)
	xorl	%esi, %esi
	callq	_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm
	leaq	112(%rsp), %rdi
	xorps	%xmm0, %xmm0
	movaps	%xmm0, 64(%rdi)
	movaps	%xmm0, 48(%rdi)
	movaps	%xmm0, 32(%rdi)
	movaps	%xmm0, 16(%rdi)
	movaps	%xmm0, (%rdi)
.Ltmp0:
	xorl	%esi, %esi
	callq	_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm
.Ltmp1:
# %bb.2:                                # %_ZNSt5queueIySt5dequeIySaIyEEEC2IS2_vEEv.exit
	leaq	16(%rsp), %rsi
	movq	$0, (%rsi)
.Ltmp3:
	leaq	32(%rsp), %rdi
	callq	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
.Ltmp4:
# %bb.3:                                # %_ZNSt5queueIySt5dequeIySaIyEEE4pushEOy.exit
	leaq	16(%rsp), %rsi
	movq	$0, (%rsi)
.Ltmp6:
	leaq	112(%rsp), %rdi
	callq	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
.Ltmp7:
# %bb.4:                                # %_ZNSt5queueIySt5dequeIySaIyEEE4pushEOy.exit30
	movq	48(%rsp), %rax
	cmpq	%rax, 80(%rsp)
	je	.LBB2_30
# %bb.5:                                # %.lr.ph
	leaq	24(%rsp), %rbp
	leaq	112(%rsp), %r13
.LBB2_6:                                # =>This Inner Loop Header: Depth=1
	movq	(%rax), %rcx
	movq	%rcx, 16(%rsp)
	movq	128(%rsp), %rcx
	movq	(%rcx), %rdx
	movq	%rdx, 8(%rsp)
	movq	64(%rsp), %rdx
	addq	$-8, %rdx
	cmpq	%rdx, %rax
	je	.LBB2_8
# %bb.7:                                #   in Loop: Header=BB2_6 Depth=1
	addq	$8, %rax
	jmp	.LBB2_9
.LBB2_8:                                #   in Loop: Header=BB2_6 Depth=1
	movq	56(%rsp), %rdi
	callq	_ZdlPv
	movq	72(%rsp), %rax
	leaq	8(%rax), %rcx
	movq	%rcx, 72(%rsp)
	movq	8(%rax), %rax
	movq	%rax, 56(%rsp)
	leaq	512(%rax), %rcx
	movq	%rcx, 64(%rsp)
	movq	128(%rsp), %rcx
.LBB2_9:                                # %_ZNSt5dequeIySaIyEE9pop_frontEv.exit
                                        #   in Loop: Header=BB2_6 Depth=1
	movq	%rax, 48(%rsp)
	movq	144(%rsp), %rax
	addq	$-8, %rax
	cmpq	%rax, %rcx
	je	.LBB2_11
# %bb.10:                               #   in Loop: Header=BB2_6 Depth=1
	addq	$8, %rcx
	jmp	.LBB2_12
.LBB2_11:                               #   in Loop: Header=BB2_6 Depth=1
	movq	136(%rsp), %rdi
	callq	_ZdlPv
	movq	152(%rsp), %rax
	leaq	8(%rax), %rcx
	movq	%rcx, 152(%rsp)
	movq	8(%rax), %rcx
	movq	%rcx, 136(%rsp)
	leaq	512(%rcx), %rax
	movq	%rax, 144(%rsp)
.LBB2_12:                               # %_ZNSt5dequeIySaIyEE9pop_frontEv.exit39
                                        #   in Loop: Header=BB2_6 Depth=1
	movq	%rcx, 128(%rsp)
	movq	16(%rsp), %rcx
	movq	(%r14,%rcx,8), %rdx
	movq	8(%rsp), %rax
	movb	$1, (%rdx,%rax)
	movq	(%r12,%rcx,8), %rdx
	cmpw	%bx, (%rdx,%rax,2)
	je	.LBB2_31
# %bb.13:                               #   in Loop: Header=BB2_6 Depth=1
	leaq	1(%rcx), %rdx
	cmpq	%r15, %rdx
	jae	.LBB2_23
# %bb.14:                               #   in Loop: Header=BB2_6 Depth=1
	movq	8(%r14,%rcx,8), %rcx
	cmpb	$0, (%rcx,%rax)
	jne	.LBB2_23
# %bb.15:                               #   in Loop: Header=BB2_6 Depth=1
	movq	%rdx, 24(%rsp)
.Ltmp9:
	leaq	32(%rsp), %rdi
	movq	%rbp, %rsi
	callq	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
.Ltmp10:
# %bb.16:                               # %_ZNSt5queueIySt5dequeIySaIyEEE4pushEOy.exit31
                                        #   in Loop: Header=BB2_6 Depth=1
	movq	160(%rsp), %rcx
	movq	176(%rsp), %rax
	addq	$-8, %rax
	cmpq	%rax, %rcx
	je	.LBB2_21
# %bb.17:                               #   in Loop: Header=BB2_6 Depth=1
	movq	8(%rsp), %rax
	movq	%rax, (%rcx)
	addq	$8, %rcx
	movq	%rcx, 160(%rsp)
	jmp	.LBB2_23
.LBB2_21:                               #   in Loop: Header=BB2_6 Depth=1
.Ltmp12:
	movq	%r13, %rdi
	leaq	8(%rsp), %rsi
	callq	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_
.Ltmp13:
# %bb.22:                               # %._ZNSt5queueIySt5dequeIySaIyEEE4pushERKy.exit_crit_edge
                                        #   in Loop: Header=BB2_6 Depth=1
	movq	8(%rsp), %rax
.LBB2_23:                               # %_ZNSt5queueIySt5dequeIySaIyEEE4pushERKy.exit
                                        #   in Loop: Header=BB2_6 Depth=1
	incq	%rax
	cmpq	%r15, %rax
	jae	.LBB2_29
# %bb.24:                               #   in Loop: Header=BB2_6 Depth=1
	movq	16(%rsp), %rcx
	movq	(%r14,%rcx,8), %rdx
	cmpb	$0, (%rdx,%rax)
	jne	.LBB2_29
# %bb.25:                               #   in Loop: Header=BB2_6 Depth=1
	movq	80(%rsp), %rax
	movq	96(%rsp), %rdx
	addq	$-8, %rdx
	cmpq	%rdx, %rax
	je	.LBB2_27
# %bb.26:                               #   in Loop: Header=BB2_6 Depth=1
	movq	%rcx, (%rax)
	addq	$8, %rax
	movq	%rax, 80(%rsp)
	jmp	.LBB2_28
.LBB2_27:                               #   in Loop: Header=BB2_6 Depth=1
.Ltmp14:
	leaq	32(%rsp), %rdi
	leaq	16(%rsp), %rsi
	callq	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_
.Ltmp15:
.LBB2_28:                               # %_ZNSt5queueIySt5dequeIySaIyEEE4pushERKy.exit34
                                        #   in Loop: Header=BB2_6 Depth=1
	movq	8(%rsp), %rax
	incq	%rax
	movq	%rax, 24(%rsp)
.Ltmp17:
	movq	%r13, %rdi
	movq	%rbp, %rsi
	callq	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
.Ltmp18:
.LBB2_29:                               #   in Loop: Header=BB2_6 Depth=1
	movq	48(%rsp), %rax
	cmpq	%rax, 80(%rsp)
	jne	.LBB2_6
.LBB2_30:
	movw	$-1, %bx
.LBB2_31:                               # %.loopexit
	leaq	112(%rsp), %rdi
	callq	_ZNSt11_Deque_baseIySaIyEED2Ev
	leaq	32(%rsp), %rdi
	callq	_ZNSt11_Deque_baseIySaIyEED2Ev
.LBB2_32:
	movl	%ebx, %eax
	addq	$200, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB2_19:
	.cfi_def_cfa_offset 256
.Ltmp8:
	jmp	.LBB2_34
.LBB2_33:
.Ltmp5:
	jmp	.LBB2_34
.LBB2_18:
.Ltmp2:
	movq	%rax, %rbx
	jmp	.LBB2_35
.LBB2_20:
.Ltmp16:
	jmp	.LBB2_34
.LBB2_37:
.Ltmp19:
	jmp	.LBB2_34
.LBB2_36:
.Ltmp11:
.LBB2_34:
	movq	%rax, %rbx
	leaq	112(%rsp), %rdi
	callq	_ZNSt11_Deque_baseIySaIyEED2Ev
.LBB2_35:
	leaq	32(%rsp), %rdi
	callq	_ZNSt11_Deque_baseIySaIyEED2Ev
	movq	%rbx, %rdi
	callq	_Unwind_Resume@PLT
.Lfunc_end2:
	.size	_Z13iterative_bfsPPsysPPb, .Lfunc_end2-_Z13iterative_bfsPPsysPPb
	.cfi_endproc
	.section	.gcc_except_table,"a",@progbits
	.p2align	2, 0x0
GCC_except_table2:
.Lexception0:
	.byte	255                             # @LPStart Encoding = omit
	.byte	255                             # @TType Encoding = omit
	.byte	1                               # Call site Encoding = uleb128
	.uleb128 .Lcst_end0-.Lcst_begin0
.Lcst_begin0:
	.uleb128 .Lfunc_begin0-.Lfunc_begin0    # >> Call Site 1 <<
	.uleb128 .Ltmp0-.Lfunc_begin0           #   Call between .Lfunc_begin0 and .Ltmp0
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp0-.Lfunc_begin0           # >> Call Site 2 <<
	.uleb128 .Ltmp1-.Ltmp0                  #   Call between .Ltmp0 and .Ltmp1
	.uleb128 .Ltmp2-.Lfunc_begin0           #     jumps to .Ltmp2
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp3-.Lfunc_begin0           # >> Call Site 3 <<
	.uleb128 .Ltmp4-.Ltmp3                  #   Call between .Ltmp3 and .Ltmp4
	.uleb128 .Ltmp5-.Lfunc_begin0           #     jumps to .Ltmp5
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp6-.Lfunc_begin0           # >> Call Site 4 <<
	.uleb128 .Ltmp7-.Ltmp6                  #   Call between .Ltmp6 and .Ltmp7
	.uleb128 .Ltmp8-.Lfunc_begin0           #     jumps to .Ltmp8
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp9-.Lfunc_begin0           # >> Call Site 5 <<
	.uleb128 .Ltmp10-.Ltmp9                 #   Call between .Ltmp9 and .Ltmp10
	.uleb128 .Ltmp11-.Lfunc_begin0          #     jumps to .Ltmp11
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp12-.Lfunc_begin0          # >> Call Site 6 <<
	.uleb128 .Ltmp15-.Ltmp12                #   Call between .Ltmp12 and .Ltmp15
	.uleb128 .Ltmp16-.Lfunc_begin0          #     jumps to .Ltmp16
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp17-.Lfunc_begin0          # >> Call Site 7 <<
	.uleb128 .Ltmp18-.Ltmp17                #   Call between .Ltmp17 and .Ltmp18
	.uleb128 .Ltmp19-.Lfunc_begin0          #     jumps to .Ltmp19
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp18-.Lfunc_begin0          # >> Call Site 8 <<
	.uleb128 .Lfunc_end2-.Ltmp18            #   Call between .Ltmp18 and .Lfunc_end2
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
.Lcst_end0:
	.p2align	2, 0x0
                                        # -- End function
	.text
	.globl	_Z13recursive_bfsPPsysPPb       # -- Begin function _Z13recursive_bfsPPsysPPb
	.type	_Z13recursive_bfsPPsysPPb,@function
_Z13recursive_bfsPPsysPPb:              # @_Z13recursive_bfsPPsysPPb
	.cfi_startproc
# %bb.0:
	movq	(%rdi), %rax
	cmpw	%dx, (%rax)
	jne	.LBB3_2
# %bb.1:
	movl	%edx, %eax
	retq
.LBB3_2:
	movq	%rcx, %r9
	movq	(%rcx), %rax
	movb	$1, (%rax)
	movswl	%dx, %edx
	xorl	%ecx, %ecx
	xorl	%r8d, %r8d
	jmp	_Z20recursive_bfs_helperPPsysyyPPb # TAILCALL
.Lfunc_end3:
	.size	_Z13recursive_bfsPPsysPPb, .Lfunc_end3-_Z13recursive_bfsPPsysPPb
	.cfi_endproc
                                        # -- End function
	.globl	_Z20recursive_bfs_helperPPsysyyPPb # -- Begin function _Z20recursive_bfs_helperPPsysyyPPb
	.type	_Z20recursive_bfs_helperPPsysyyPPb,@function
_Z20recursive_bfs_helperPPsysyyPPb:     # @_Z20recursive_bfs_helperPPsysyyPPb
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movq	%r9, %rbx
	movq	%r8, %r13
	movq	%rcx, %r15
	movq	%rsi, %r12
	leaq	1(%rcx), %rbp
	movswl	%dx, %eax
	movl	%eax, 12(%rsp)                  # 4-byte Spill
	movl	%edx, 8(%rsp)                   # 4-byte Spill
	movq	%rdi, 16(%rsp)                  # 8-byte Spill
.LBB4_1:                                # %tailrecurse
                                        # =>This Inner Loop Header: Depth=1
	cmpq	%r12, %rbp
	jae	.LBB4_4
# %bb.2:                                #   in Loop: Header=BB4_1 Depth=1
	movq	8(%rdi,%r15,8), %rax
	cmpw	%dx, (%rax,%r13,2)
	je	.LBB4_3
.LBB4_4:                                #   in Loop: Header=BB4_1 Depth=1
	leaq	1(%r13), %r14
	cmpq	%r12, %r14
	jae	.LBB4_6
# %bb.5:                                #   in Loop: Header=BB4_1 Depth=1
	movq	(%rdi,%r15,8), %rax
	cmpw	%dx, (%rax,%r14,2)
	je	.LBB4_3
.LBB4_6:                                #   in Loop: Header=BB4_1 Depth=1
	cmpq	%r12, %rbp
	jae	.LBB4_12
# %bb.7:                                #   in Loop: Header=BB4_1 Depth=1
	movq	8(%rbx,%r15,8), %rax
	cmpb	$0, (%rax,%r13)
	je	.LBB4_8
.LBB4_12:                               # %.thread
                                        #   in Loop: Header=BB4_1 Depth=1
	cmpq	%r12, %r14
	jae	.LBB4_13
.LBB4_10:                               #   in Loop: Header=BB4_1 Depth=1
	movq	(%rbx,%r15,8), %rax
	cmpb	$0, 1(%rax,%r13)
	jne	.LBB4_13
# %bb.11:                               #   in Loop: Header=BB4_1 Depth=1
	movb	$1, 1(%rax,%r13)
	movq	%r14, %r13
	jmp	.LBB4_1
.LBB4_8:                                #   in Loop: Header=BB4_1 Depth=1
	movb	$1, (%rax,%r13)
	movq	%r12, %rsi
	movl	12(%rsp), %edx                  # 4-byte Reload
	movq	%rbp, %rcx
	movq	%r13, %r8
	movq	%rbx, %r9
	callq	_Z20recursive_bfs_helperPPsysyyPPb
	cmpq	%r12, %r14
	jae	.LBB4_14
# %bb.9:                                #   in Loop: Header=BB4_1 Depth=1
	cmpw	$-1, %ax
	movl	8(%rsp), %edx                   # 4-byte Reload
	movq	16(%rsp), %rdi                  # 8-byte Reload
	je	.LBB4_10
	jmp	.LBB4_14
.LBB4_13:
	movw	$-1, %ax
	jmp	.LBB4_14
.LBB4_3:
	movl	%edx, %eax
.LBB4_14:
	addq	$24, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end4:
	.size	_Z20recursive_bfs_helperPPsysyyPPb, .Lfunc_end4-_Z20recursive_bfs_helperPPsysyyPPb
	.cfi_endproc
                                        # -- End function
	.globl	_Z25__device_stub__bfs_kernelPsPiS0_ys # -- Begin function _Z25__device_stub__bfs_kernelPsPiS0_ys
	.type	_Z25__device_stub__bfs_kernelPsPiS0_ys,@function
_Z25__device_stub__bfs_kernelPsPiS0_ys: # @_Z25__device_stub__bfs_kernelPsPiS0_ys
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r13
	.cfi_def_cfa_offset 32
	pushq	%r12
	.cfi_def_cfa_offset 40
	pushq	%rbx
	.cfi_def_cfa_offset 48
	subq	$144, %rsp
	.cfi_def_cfa_offset 192
	.cfi_offset %rbx, -48
	.cfi_offset %r12, -40
	.cfi_offset %r13, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	leaq	56(%rsp), %rax
	movq	%rdi, (%rax)
	leaq	48(%rsp), %rdi
	movq	%rsi, (%rdi)
	leaq	40(%rsp), %rsi
	movq	%rdx, (%rsi)
	leaq	32(%rsp), %rdx
	movq	%rcx, (%rdx)
	leaq	14(%rsp), %rcx
	movw	%r8w, (%rcx)
	leaq	96(%rsp), %rbx
	movq	%rax, (%rbx)
	movq	%rdi, 8(%rbx)
	movq	%rsi, 16(%rbx)
	movq	%rdx, 24(%rbx)
	movq	%rcx, 32(%rbx)
	leaq	80(%rsp), %r14
	leaq	64(%rsp), %r15
	leaq	24(%rsp), %r12
	leaq	16(%rsp), %r13
	movq	%r14, %rdi
	movq	%r15, %rsi
	movq	%r12, %rdx
	movq	%r13, %rcx
	callq	__hipPopCallConfiguration
	movq	(%r14), %rsi
	movl	8(%r14), %edx
	movq	(%r15), %rcx
	movl	8(%r15), %r8d
	movl	$_Z10bfs_kernelPsPiS0_ys, %edi
	movq	%rbx, %r9
	pushq	(%r13)
	.cfi_adjust_cfa_offset 8
	pushq	(%r12)
	.cfi_adjust_cfa_offset 8
	callq	hipLaunchKernel
	addq	$160, %rsp
	.cfi_adjust_cfa_offset -160
	popq	%rbx
	.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
	retq
.Lfunc_end5:
	.size	_Z25__device_stub__bfs_kernelPsPiS0_ys, .Lfunc_end5-_Z25__device_stub__bfs_kernelPsPiS0_ys
	.cfi_endproc
                                        # -- End function
	.section	.text.__clang_call_terminate,"axG",@progbits,__clang_call_terminate,comdat
	.hidden	__clang_call_terminate          # -- Begin function __clang_call_terminate
	.weak	__clang_call_terminate
	.type	__clang_call_terminate,@function
__clang_call_terminate:                 # @__clang_call_terminate
	.cfi_startproc
# %bb.0:
	pushq	%rax
	.cfi_def_cfa_offset 16
	callq	__cxa_begin_catch
	callq	_ZSt9terminatev
.Lfunc_end6:
	.size	__clang_call_terminate, .Lfunc_end6-__clang_call_terminate
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt11_Deque_baseIySaIyEED2Ev,"axG",@progbits,_ZNSt11_Deque_baseIySaIyEED2Ev,comdat
	.weak	_ZNSt11_Deque_baseIySaIyEED2Ev  # -- Begin function _ZNSt11_Deque_baseIySaIyEED2Ev
	.p2align	1, 0x90
	.type	_ZNSt11_Deque_baseIySaIyEED2Ev,@function
_ZNSt11_Deque_baseIySaIyEED2Ev:         # @_ZNSt11_Deque_baseIySaIyEED2Ev
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rdi, %rbx
	movq	(%rdi), %rdi
	testq	%rdi, %rdi
	je	.LBB7_6
# %bb.1:
	movq	40(%rbx), %r14
	movq	72(%rbx), %r15
	leaq	8(%r15), %rax
	cmpq	%rax, %r14
	jae	.LBB7_5
# %bb.2:                                # %.lr.ph.i.preheader
	addq	$-8, %r14
.LBB7_3:                                # %.lr.ph.i
                                        # =>This Inner Loop Header: Depth=1
	movq	8(%r14), %rdi
	addq	$8, %r14
	callq	_ZdlPv
	cmpq	%r15, %r14
	jb	.LBB7_3
# %bb.4:                                # %_ZNSt11_Deque_baseIySaIyEE16_M_destroy_nodesEPPyS3_.exit.loopexit
	movq	(%rbx), %rdi
.LBB7_5:                                # %_ZNSt11_Deque_baseIySaIyEE16_M_destroy_nodesEPPyS3_.exit
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	jmp	_ZdlPv                          # TAILCALL
.LBB7_6:
	.cfi_def_cfa_offset 32
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end7:
	.size	_ZNSt11_Deque_baseIySaIyEED2Ev, .Lfunc_end7-_ZNSt11_Deque_baseIySaIyEED2Ev
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm,"axG",@progbits,_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm,comdat
	.weak	_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm # -- Begin function _ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm
	.p2align	1, 0x90
	.type	_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm,@function
_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm: # @_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm
.Lfunc_begin1:
	.cfi_startproc
	.cfi_personality 3, __gxx_personality_v0
	.cfi_lsda 3, .Lexception1
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%r12
	.cfi_def_cfa_offset 32
	pushq	%rbx
	.cfi_def_cfa_offset 40
	pushq	%rax
	.cfi_def_cfa_offset 48
	.cfi_offset %rbx, -40
	.cfi_offset %r12, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	%rsi, %r14
	movq	%rdi, %rbx
	movq	%rsi, %r12
	shrq	$6, %r12
	leaq	1(%r12), %r15
	cmpq	$6, %r12
	movl	$5, %esi
	cmovaeq	%r12, %rsi
	addq	$3, %rsi
	movq	%rsi, 8(%rdi)
	leaq	7(%rsp), %rdi
	xorl	%edx, %edx
	callq	_ZNSt15__new_allocatorIPyE8allocateEmPKv
	movq	%rax, (%rbx)
	movq	8(%rbx), %rcx
	subq	%r15, %rcx
	andq	$-2, %rcx
	leaq	(%rax,%rcx,4), %r15
	leaq	(%r15,%r12,8), %rdx
	addq	$8, %rdx
.Ltmp20:
	movq	%rbx, %rdi
	movq	%r15, %rsi
	callq	_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_
.Ltmp21:
# %bb.1:
	movq	%r15, 40(%rbx)
	movq	(%r15), %rax
	movq	%rax, 24(%rbx)
	movl	$512, %ecx                      # imm = 0x200
	leaq	(%rax,%rcx), %rdx
	movq	%rdx, 32(%rbx)
	leaq	(%r15,%r12,8), %rdx
	movq	%rdx, 72(%rbx)
	movq	(%rdx), %rdx
	movq	%rdx, 56(%rbx)
	addq	%rdx, %rcx
	movq	%rcx, 64(%rbx)
	movq	%rax, 16(%rbx)
	andl	$63, %r14d
	leaq	(%rdx,%r14,8), %rax
	movq	%rax, 48(%rbx)
	addq	$8, %rsp
	.cfi_def_cfa_offset 40
	popq	%rbx
	.cfi_def_cfa_offset 32
	popq	%r12
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB8_5:
	.cfi_def_cfa_offset 48
.Ltmp22:
	movq	%rax, %rdi
	callq	__cxa_begin_catch
	movq	(%rbx), %rdi
	callq	_ZdlPv
	xorps	%xmm0, %xmm0
	movups	%xmm0, (%rbx)
.Ltmp23:
	callq	__cxa_rethrow
.Ltmp24:
# %bb.6:
.LBB8_2:
.Ltmp25:
	movq	%rax, %rbx
.Ltmp26:
	callq	__cxa_end_catch
.Ltmp27:
# %bb.3:
	movq	%rbx, %rdi
	callq	_Unwind_Resume@PLT
.LBB8_4:
.Ltmp28:
	movq	%rax, %rdi
	callq	__clang_call_terminate
.Lfunc_end8:
	.size	_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm, .Lfunc_end8-_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm
	.cfi_endproc
	.section	.gcc_except_table._ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm,"aG",@progbits,_ZNSt11_Deque_baseIySaIyEE17_M_initialize_mapEm,comdat
	.p2align	2, 0x0
GCC_except_table8:
.Lexception1:
	.byte	255                             # @LPStart Encoding = omit
	.byte	3                               # @TType Encoding = udata4
	.uleb128 .Lttbase0-.Lttbaseref0
.Lttbaseref0:
	.byte	1                               # Call site Encoding = uleb128
	.uleb128 .Lcst_end1-.Lcst_begin1
.Lcst_begin1:
	.uleb128 .Lfunc_begin1-.Lfunc_begin1    # >> Call Site 1 <<
	.uleb128 .Ltmp20-.Lfunc_begin1          #   Call between .Lfunc_begin1 and .Ltmp20
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp20-.Lfunc_begin1          # >> Call Site 2 <<
	.uleb128 .Ltmp21-.Ltmp20                #   Call between .Ltmp20 and .Ltmp21
	.uleb128 .Ltmp22-.Lfunc_begin1          #     jumps to .Ltmp22
	.byte	1                               #   On action: 1
	.uleb128 .Ltmp21-.Lfunc_begin1          # >> Call Site 3 <<
	.uleb128 .Ltmp23-.Ltmp21                #   Call between .Ltmp21 and .Ltmp23
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp23-.Lfunc_begin1          # >> Call Site 4 <<
	.uleb128 .Ltmp24-.Ltmp23                #   Call between .Ltmp23 and .Ltmp24
	.uleb128 .Ltmp25-.Lfunc_begin1          #     jumps to .Ltmp25
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp26-.Lfunc_begin1          # >> Call Site 5 <<
	.uleb128 .Ltmp27-.Ltmp26                #   Call between .Ltmp26 and .Ltmp27
	.uleb128 .Ltmp28-.Lfunc_begin1          #     jumps to .Ltmp28
	.byte	1                               #   On action: 1
	.uleb128 .Ltmp27-.Lfunc_begin1          # >> Call Site 6 <<
	.uleb128 .Lfunc_end8-.Ltmp27            #   Call between .Ltmp27 and .Lfunc_end8
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
.Lcst_end1:
	.byte	1                               # >> Action Record 1 <<
                                        #   Catch TypeInfo 1
	.byte	0                               #   No further actions
	.p2align	2, 0x0
                                        # >> Catch TypeInfos <<
	.long	0                               # TypeInfo 1
.Lttbase0:
	.p2align	2, 0x0
                                        # -- End function
	.section	.text._ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_,"axG",@progbits,_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_,comdat
	.weak	_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_ # -- Begin function _ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_
	.p2align	1, 0x90
	.type	_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_,@function
_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_: # @_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_
.Lfunc_begin2:
	.cfi_startproc
	.cfi_personality 3, __gxx_personality_v0
	.cfi_lsda 3, .Lexception2
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	cmpq	%rdx, %rsi
	jae	.LBB9_4
# %bb.1:                                # %.lr.ph.preheader
	movq	%rdx, %r14
	movq	%rsi, %rbx
	movq	%rsi, %r15
.LBB9_2:                                # %.lr.ph
                                        # =>This Inner Loop Header: Depth=1
.Ltmp29:
	movl	$512, %edi                      # imm = 0x200
	callq	_Znwm
.Ltmp30:
# %bb.3:                                # %_ZNSt11_Deque_baseIySaIyEE16_M_allocate_nodeEv.exit
                                        #   in Loop: Header=BB9_2 Depth=1
	movq	%rax, (%r15)
	addq	$8, %r15
	cmpq	%r14, %r15
	jb	.LBB9_2
.LBB9_4:                                # %._crit_edge
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB9_5:
	.cfi_def_cfa_offset 32
.Ltmp31:
	movq	%rax, %rdi
	callq	__cxa_begin_catch
	cmpq	%rbx, %r15
	jbe	.LBB9_7
.LBB9_6:                                # %.lr.ph.i
                                        # =>This Inner Loop Header: Depth=1
	movq	(%rbx), %rdi
	callq	_ZdlPv
	addq	$8, %rbx
	cmpq	%r15, %rbx
	jb	.LBB9_6
.LBB9_7:                                # %_ZNSt11_Deque_baseIySaIyEE16_M_destroy_nodesEPPyS3_.exit
.Ltmp32:
	callq	__cxa_rethrow
.Ltmp33:
# %bb.11:
.LBB9_8:
.Ltmp34:
	movq	%rax, %rbx
.Ltmp35:
	callq	__cxa_end_catch
.Ltmp36:
# %bb.9:
	movq	%rbx, %rdi
	callq	_Unwind_Resume@PLT
.LBB9_10:
.Ltmp37:
	movq	%rax, %rdi
	callq	__clang_call_terminate
.Lfunc_end9:
	.size	_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_, .Lfunc_end9-_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_
	.cfi_endproc
	.section	.gcc_except_table._ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_,"aG",@progbits,_ZNSt11_Deque_baseIySaIyEE15_M_create_nodesEPPyS3_,comdat
	.p2align	2, 0x0
GCC_except_table9:
.Lexception2:
	.byte	255                             # @LPStart Encoding = omit
	.byte	3                               # @TType Encoding = udata4
	.uleb128 .Lttbase1-.Lttbaseref1
.Lttbaseref1:
	.byte	1                               # Call site Encoding = uleb128
	.uleb128 .Lcst_end2-.Lcst_begin2
.Lcst_begin2:
	.uleb128 .Ltmp29-.Lfunc_begin2          # >> Call Site 1 <<
	.uleb128 .Ltmp30-.Ltmp29                #   Call between .Ltmp29 and .Ltmp30
	.uleb128 .Ltmp31-.Lfunc_begin2          #     jumps to .Ltmp31
	.byte	1                               #   On action: 1
	.uleb128 .Ltmp30-.Lfunc_begin2          # >> Call Site 2 <<
	.uleb128 .Ltmp32-.Ltmp30                #   Call between .Ltmp30 and .Ltmp32
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp32-.Lfunc_begin2          # >> Call Site 3 <<
	.uleb128 .Ltmp33-.Ltmp32                #   Call between .Ltmp32 and .Ltmp33
	.uleb128 .Ltmp34-.Lfunc_begin2          #     jumps to .Ltmp34
	.byte	0                               #   On action: cleanup
	.uleb128 .Ltmp35-.Lfunc_begin2          # >> Call Site 4 <<
	.uleb128 .Ltmp36-.Ltmp35                #   Call between .Ltmp35 and .Ltmp36
	.uleb128 .Ltmp37-.Lfunc_begin2          #     jumps to .Ltmp37
	.byte	1                               #   On action: 1
	.uleb128 .Ltmp36-.Lfunc_begin2          # >> Call Site 5 <<
	.uleb128 .Lfunc_end9-.Ltmp36            #   Call between .Ltmp36 and .Lfunc_end9
	.byte	0                               #     has no landing pad
	.byte	0                               #   On action: cleanup
.Lcst_end2:
	.byte	1                               # >> Action Record 1 <<
                                        #   Catch TypeInfo 1
	.byte	0                               #   No further actions
	.p2align	2, 0x0
                                        # >> Catch TypeInfos <<
	.long	0                               # TypeInfo 1
.Lttbase1:
	.p2align	2, 0x0
                                        # -- End function
	.section	.text._ZNSt15__new_allocatorIPyE8allocateEmPKv,"axG",@progbits,_ZNSt15__new_allocatorIPyE8allocateEmPKv,comdat
	.weak	_ZNSt15__new_allocatorIPyE8allocateEmPKv # -- Begin function _ZNSt15__new_allocatorIPyE8allocateEmPKv
	.p2align	1, 0x90
	.type	_ZNSt15__new_allocatorIPyE8allocateEmPKv,@function
_ZNSt15__new_allocatorIPyE8allocateEmPKv: # @_ZNSt15__new_allocatorIPyE8allocateEmPKv
	.cfi_startproc
# %bb.0:
	pushq	%rax
	.cfi_def_cfa_offset 16
	movq	%rsi, %rax
	shrq	$60, %rax
	jne	.LBB10_1
# %bb.3:
	shlq	$3, %rsi
	movq	%rsi, %rdi
	popq	%rax
	.cfi_def_cfa_offset 8
	jmp	_Znwm                           # TAILCALL
.LBB10_1:
	.cfi_def_cfa_offset 16
	shrq	$61, %rsi
	je	.LBB10_2
# %bb.4:
	callq	_ZSt28__throw_bad_array_new_lengthv
.LBB10_2:
	callq	_ZSt17__throw_bad_allocv
.Lfunc_end10:
	.size	_ZNSt15__new_allocatorIPyE8allocateEmPKv, .Lfunc_end10-_ZNSt15__new_allocatorIPyE8allocateEmPKv
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_,"axG",@progbits,_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_,comdat
	.weak	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_ # -- Begin function _ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
	.p2align	1, 0x90
	.type	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_,@function
_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_: # @_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
	.cfi_startproc
# %bb.0:
	pushq	%rbx
	.cfi_def_cfa_offset 16
	.cfi_offset %rbx, -16
	movq	%rdi, %rbx
	movq	48(%rdi), %rax
	movq	64(%rdi), %rcx
	addq	$-8, %rcx
	cmpq	%rcx, %rax
	je	.LBB11_2
# %bb.1:
	movq	(%rsi), %rcx
	movq	%rcx, (%rax)
	addq	$8, %rax
	movq	%rax, 48(%rbx)
	jmp	.LBB11_3
.LBB11_2:
	movq	%rbx, %rdi
	callq	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_
	movq	48(%rbx), %rax
.LBB11_3:
	cmpq	56(%rbx), %rax
	jne	.LBB11_5
# %bb.4:
	movq	72(%rbx), %rcx
	movl	$512, %eax                      # imm = 0x200
	addq	-8(%rcx), %rax
.LBB11_5:                               # %_ZNSt5dequeIySaIyEE4backEv.exit
	addq	$-8, %rax
	popq	%rbx
	.cfi_def_cfa_offset 8
	retq
.Lfunc_end11:
	.size	_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_, .Lfunc_end11-_ZNSt5dequeIySaIyEE12emplace_backIJyEEERyDpOT_
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_,"axG",@progbits,_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_,comdat
	.weak	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_ # -- Begin function _ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_
	.p2align	1, 0x90
	.type	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_,@function
_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_: # @_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	72(%rdi), %r15
	movq	%r15, %rax
	subq	40(%rdi), %rax
	shrq	$3, %rax
	cmpq	$1, %r15
	adcq	$-1, %rax
	shlq	$6, %rax
	movq	32(%rdi), %rcx
	movq	48(%rdi), %rdx
	subq	56(%rdi), %rdx
	sarq	$3, %rdx
	subq	16(%rdi), %rcx
	sarq	$3, %rcx
	addq	%rdx, %rcx
	addq	%rax, %rcx
	movabsq	$1152921504606846975, %rax      # imm = 0xFFFFFFFFFFFFFFF
	cmpq	%rax, %rcx
	je	.LBB12_4
# %bb.1:
	movq	%rsi, %r14
	movq	%rdi, %rbx
	movq	%r15, %rax
	subq	(%rdi), %rax
	movq	8(%rdi), %rcx
	sarq	$3, %rax
	subq	%rax, %rcx
	cmpq	$1, %rcx
	ja	.LBB12_3
# %bb.2:
	movl	$1, %esi
	movq	%rbx, %rdi
	xorl	%edx, %edx
	callq	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	movq	72(%rbx), %r15
.LBB12_3:                               # %_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm.exit
	movl	$512, %edi                      # imm = 0x200
	callq	_Znwm
	movq	%rax, 8(%r15)
	movq	48(%rbx), %rax
	movq	(%r14), %rcx
	movq	%rcx, (%rax)
	movq	72(%rbx), %rax
	leaq	8(%rax), %rcx
	movq	%rcx, 72(%rbx)
	movq	8(%rax), %rax
	movq	%rax, 56(%rbx)
	leaq	512(%rax), %rcx
	movq	%rcx, 64(%rbx)
	movq	%rax, 48(%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB12_4:
	.cfi_def_cfa_offset 32
	movl	$.L.str.10, %edi
	callq	_ZSt20__throw_length_errorPKc
.Lfunc_end12:
	.size	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_, .Lfunc_end12-_ZNSt5dequeIySaIyEE16_M_push_back_auxIJyEEEvDpOT_
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb,"axG",@progbits,_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb,comdat
	.weak	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb # -- Begin function _ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	.p2align	1, 0x90
	.type	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb,@function
_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb: # @_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	.cfi_startproc
# %bb.0:
	pushq	%rbp
	.cfi_def_cfa_offset 16
	pushq	%r15
	.cfi_def_cfa_offset 24
	pushq	%r14
	.cfi_def_cfa_offset 32
	pushq	%r13
	.cfi_def_cfa_offset 40
	pushq	%r12
	.cfi_def_cfa_offset 48
	pushq	%rbx
	.cfi_def_cfa_offset 56
	subq	$24, %rsp
	.cfi_def_cfa_offset 80
	.cfi_offset %rbx, -56
	.cfi_offset %r12, -48
	.cfi_offset %r13, -40
	.cfi_offset %r14, -32
	.cfi_offset %r15, -24
	.cfi_offset %rbp, -16
	movl	%edx, %r8d
	movq	%rsi, %r14
	movq	%rdi, %rbx
	movq	72(%rdi), %rax
	movq	8(%rdi), %rcx
	movq	40(%rdi), %rsi
	subq	%rsi, %rax
	movq	%rax, %r13
	sarq	$3, %r13
	leaq	(%r14,%r13), %r12
	incq	%r12
	incq	%r13
	leaq	(%r12,%r12), %rdx
	cmpq	%rdx, %rcx
	jbe	.LBB13_4
# %bb.1:
	subq	%r12, %rcx
	andq	$-2, %rcx
	shlq	$2, %rcx
	addq	(%rbx), %rcx
	xorl	%edx, %edx
	testb	%r8b, %r8b
	cmovneq	%r14, %rdx
	leaq	(%rcx,%rdx,8), %r14
	leaq	8(%rax), %rdx
	cmpq	%rsi, %r14
	jae	.LBB13_7
# %bb.2:
	cmpq	$9, %rdx
	jl	.LBB13_13
# %bb.3:
	movq	%r14, %rdi
	jmp	.LBB13_9
.LBB13_4:
	cmpq	%r14, %rcx
	movq	%r14, %rax
	cmovaq	%rcx, %rax
	leaq	(%rcx,%rax), %rbp
	addq	$2, %rbp
	xorl	%r15d, %r15d
	leaq	11(%rsp), %rdi
	movq	%rbp, %rsi
	xorl	%edx, %edx
	movl	%r8d, 12(%rsp)                  # 4-byte Spill
	callq	_ZNSt15__new_allocatorIPyE8allocateEmPKv
	movq	%rbp, 16(%rsp)                  # 8-byte Spill
	subq	%r12, %rbp
	movq	%rax, %r12
	andq	$-2, %rbp
	leaq	(%rax,%rbp,4), %rax
	cmpb	$0, 12(%rsp)                    # 1-byte Folded Reload
	cmovneq	%r14, %r15
	leaq	(%rax,%r15,8), %r14
	movq	40(%rbx), %rsi
	movq	72(%rbx), %rdx
	subq	%rsi, %rdx
	addq	$8, %rdx
	cmpq	$9, %rdx
	jl	.LBB13_11
# %bb.5:
	movq	%r14, %rdi
	callq	memmove@PLT
.LBB13_6:                               # %_ZSt4copyIPPyS1_ET0_T_S3_S2_.exit24
	movq	(%rbx), %rdi
	callq	_ZdlPv
	movq	%r12, (%rbx)
	movq	16(%rsp), %rax                  # 8-byte Reload
	movq	%rax, 8(%rbx)
	jmp	.LBB13_10
.LBB13_7:
	movq	%rdx, %rcx
	sarq	$3, %rcx
	cmpq	$2, %rcx
	jl	.LBB13_15
# %bb.8:
	leaq	(%r14,%r13,8), %rdi
	shlq	$3, %rcx
	subq	%rcx, %rdi
.LBB13_9:                               # %_ZSt4copyIPPyS1_ET0_T_S3_S2_.exit
	callq	memmove@PLT
.LBB13_10:                              # %_ZSt4copyIPPyS1_ET0_T_S3_S2_.exit
	movq	%r14, 40(%rbx)
	movq	(%r14), %rax
	movq	%rax, 24(%rbx)
	movl	$512, %ecx                      # imm = 0x200
	addq	%rcx, %rax
	movq	%rax, 32(%rbx)
	leaq	(%r14,%r13,8), %rax
	addq	$-8, %rax
	movq	%rax, 72(%rbx)
	movq	(%rax), %rax
	movq	%rax, 56(%rbx)
	addq	%rcx, %rax
	movq	%rax, 64(%rbx)
	addq	$24, %rsp
	.cfi_def_cfa_offset 56
	popq	%rbx
	.cfi_def_cfa_offset 48
	popq	%r12
	.cfi_def_cfa_offset 40
	popq	%r13
	.cfi_def_cfa_offset 32
	popq	%r14
	.cfi_def_cfa_offset 24
	popq	%r15
	.cfi_def_cfa_offset 16
	popq	%rbp
	.cfi_def_cfa_offset 8
	retq
.LBB13_11:
	.cfi_def_cfa_offset 80
	cmpq	$8, %rdx
	jne	.LBB13_6
# %bb.12:
	movq	(%rsi), %rax
	movq	%rax, (%r14)
	jmp	.LBB13_6
.LBB13_13:
	cmpq	$8, %rdx
	jne	.LBB13_10
# %bb.14:
	movq	(%rsi), %rax
	movq	%rax, (%r14)
	jmp	.LBB13_10
.LBB13_15:
	cmpq	$8, %rdx
	jne	.LBB13_10
# %bb.16:
	movq	(%rsi), %rcx
	movq	%rcx, (%r14,%rax)
	jmp	.LBB13_10
.Lfunc_end13:
	.size	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb, .Lfunc_end13-_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	.cfi_endproc
                                        # -- End function
	.section	.text._ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_,"axG",@progbits,_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_,comdat
	.weak	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_ # -- Begin function _ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_
	.p2align	1, 0x90
	.type	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_,@function
_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_: # @_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_
	.cfi_startproc
# %bb.0:
	pushq	%r15
	.cfi_def_cfa_offset 16
	pushq	%r14
	.cfi_def_cfa_offset 24
	pushq	%rbx
	.cfi_def_cfa_offset 32
	.cfi_offset %rbx, -32
	.cfi_offset %r14, -24
	.cfi_offset %r15, -16
	movq	72(%rdi), %r15
	movq	%r15, %rax
	subq	40(%rdi), %rax
	shrq	$3, %rax
	cmpq	$1, %r15
	adcq	$-1, %rax
	shlq	$6, %rax
	movq	32(%rdi), %rcx
	movq	48(%rdi), %rdx
	subq	56(%rdi), %rdx
	sarq	$3, %rdx
	subq	16(%rdi), %rcx
	sarq	$3, %rcx
	addq	%rdx, %rcx
	addq	%rax, %rcx
	movabsq	$1152921504606846975, %rax      # imm = 0xFFFFFFFFFFFFFFF
	cmpq	%rax, %rcx
	je	.LBB14_4
# %bb.1:
	movq	%rsi, %r14
	movq	%rdi, %rbx
	movq	%r15, %rax
	subq	(%rdi), %rax
	movq	8(%rdi), %rcx
	sarq	$3, %rax
	subq	%rax, %rcx
	cmpq	$1, %rcx
	ja	.LBB14_3
# %bb.2:
	movl	$1, %esi
	movq	%rbx, %rdi
	xorl	%edx, %edx
	callq	_ZNSt5dequeIySaIyEE17_M_reallocate_mapEmb
	movq	72(%rbx), %r15
.LBB14_3:                               # %_ZNSt5dequeIySaIyEE22_M_reserve_map_at_backEm.exit
	movl	$512, %edi                      # imm = 0x200
	callq	_Znwm
	movq	%rax, 8(%r15)
	movq	48(%rbx), %rax
	movq	(%r14), %rcx
	movq	%rcx, (%rax)
	movq	72(%rbx), %rax
	leaq	8(%rax), %rcx
	movq	%rcx, 72(%rbx)
	movq	8(%rax), %rax
	movq	%rax, 56(%rbx)
	leaq	512(%rax), %rcx
	movq	%rcx, 64(%rbx)
	movq	%rax, 48(%rbx)
	popq	%rbx
	.cfi_def_cfa_offset 24
	popq	%r14
	.cfi_def_cfa_offset 16
	popq	%r15
	.cfi_def_cfa_offset 8
	retq
.LBB14_4:
	.cfi_def_cfa_offset 32
	movl	$.L.str.10, %edi
	callq	_ZSt20__throw_length_errorPKc
.Lfunc_end14:
	.size	_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_, .Lfunc_end14-_ZNSt5dequeIySaIyEE16_M_push_back_auxIJRKyEEEvDpOT_
	.cfi_endproc
                                        # -- End function
	.text
	.p2align	4, 0x90                         # -- Begin function __hip_module_ctor
	.type	__hip_module_ctor,@function
__hip_module_ctor:                      # @__hip_module_ctor
	.cfi_startproc
# %bb.0:
	subq	$40, %rsp
	.cfi_def_cfa_offset 48
	movq	__hip_gpubin_handle(%rip), %rdi
	testq	%rdi, %rdi
	jne	.LBB15_2
# %bb.1:
	movl	$__hip_fatbin_wrapper, %edi
	callq	__hipRegisterFatBinary
	movq	%rax, %rdi
	movq	%rax, __hip_gpubin_handle(%rip)
.LBB15_2:
	xorps	%xmm0, %xmm0
	movups	%xmm0, 16(%rsp)
	movups	%xmm0, (%rsp)
	movl	$_Z10bfs_kernelPsPiS0_ys, %esi
	movl	$.L__unnamed_1, %edx
	movl	$.L__unnamed_1, %ecx
	movl	$-1, %r8d
	xorl	%r9d, %r9d
	callq	__hipRegisterFunction
	movl	$__hip_module_dtor, %edi
	addq	$40, %rsp
	.cfi_def_cfa_offset 8
	jmp	atexit                          # TAILCALL
.Lfunc_end15:
	.size	__hip_module_ctor, .Lfunc_end15-__hip_module_ctor
	.cfi_endproc
                                        # -- End function
	.p2align	4, 0x90                         # -- Begin function __hip_module_dtor
	.type	__hip_module_dtor,@function
__hip_module_dtor:                      # @__hip_module_dtor
	.cfi_startproc
# %bb.0:
	movq	__hip_gpubin_handle(%rip), %rdi
	testq	%rdi, %rdi
	je	.LBB16_2
# %bb.1:
	pushq	%rax
	.cfi_def_cfa_offset 16
	callq	__hipUnregisterFatBinary
	movq	$0, __hip_gpubin_handle(%rip)
	addq	$8, %rsp
	.cfi_def_cfa_offset 8
.LBB16_2:
	retq
.Lfunc_end16:
	.size	__hip_module_dtor, .Lfunc_end16-__hip_module_dtor
	.cfi_endproc
                                        # -- End function
	.type	.L.str,@object                  # @.str
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str:
	.asciz	"Enter N (NxN matrix): "
	.size	.L.str, 23

	.type	.L.str.1,@object                # @.str.1
.L.str.1:
	.asciz	"Enter target integer [0 to 100]: "
	.size	.L.str.1, 34

	.type	.L.str.2,@object                # @.str.2
.L.str.2:
	.asciz	"----------------------------------------------------------"
	.size	.L.str.2, 59

	.type	.L.str.3,@object                # @.str.3
.L.str.3:
	.asciz	"Found: "
	.size	.L.str.3, 8

	.type	.L.str.4,@object                # @.str.4
.L.str.4:
	.asciz	"[CUDA] Elapsed time: "
	.size	.L.str.4, 22

	.type	.L.str.5,@object                # @.str.5
.L.str.5:
	.asciz	" clock cycles"
	.size	.L.str.5, 14

	.type	.L.str.6,@object                # @.str.6
.L.str.6:
	.asciz	"Starting sequential iterative approach."
	.size	.L.str.6, 40

	.type	.L.str.7,@object                # @.str.7
.L.str.7:
	.asciz	"[SEQUENTIAL - Iterative] Elapsed time: "
	.size	.L.str.7, 40

	.type	.L.str.8,@object                # @.str.8
.L.str.8:
	.asciz	"Starting sequential recursive approach."
	.size	.L.str.8, 40

	.type	.L.str.9,@object                # @.str.9
.L.str.9:
	.asciz	"[SEQUENTIAL - Recursive] Elapsed time: "
	.size	.L.str.9, 40

	.type	_Z10bfs_kernelPsPiS0_ys,@object # @_Z10bfs_kernelPsPiS0_ys
	.section	.rodata,"a",@progbits
	.globl	_Z10bfs_kernelPsPiS0_ys
	.p2align	3, 0x0
_Z10bfs_kernelPsPiS0_ys:
	.quad	_Z25__device_stub__bfs_kernelPsPiS0_ys
	.size	_Z10bfs_kernelPsPiS0_ys, 8

	.type	.L.str.10,@object               # @.str.10
	.section	.rodata.str1.1,"aMS",@progbits,1
.L.str.10:
	.asciz	"cannot create std::deque larger than max_size()"
	.size	.L.str.10, 48

	.type	.L__unnamed_1,@object           # @0
.L__unnamed_1:
	.asciz	"_Z10bfs_kernelPsPiS0_ys"
	.size	.L__unnamed_1, 24

	.type	__hip_fatbin_wrapper,@object    # @__hip_fatbin_wrapper
	.section	.hipFatBinSegment,"a",@progbits
	.p2align	3, 0x0
__hip_fatbin_wrapper:
	.long	1212764230                      # 0x48495046
	.long	1                               # 0x1
	.quad	__hip_fatbin
	.quad	0
	.size	__hip_fatbin_wrapper, 24

	.type	__hip_gpubin_handle,@object     # @__hip_gpubin_handle
	.local	__hip_gpubin_handle
	.comm	__hip_gpubin_handle,8,8
	.section	.init_array,"aw",@init_array
	.p2align	3, 0x0
	.quad	__hip_module_ctor
	.type	__hip_cuid_,@object             # @__hip_cuid_
	.bss
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               # 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __gxx_personality_v0
	.addrsig_sym _Z25__device_stub__bfs_kernelPsPiS0_ys
	.addrsig_sym __hip_module_ctor
	.addrsig_sym __hip_module_dtor
	.addrsig_sym _Unwind_Resume
	.addrsig_sym _ZSt4cout
	.addrsig_sym _ZSt3cin
	.addrsig_sym _Z10bfs_kernelPsPiS0_ys
	.addrsig_sym __hip_fatbin
	.addrsig_sym __hip_fatbin_wrapper
	.addrsig_sym __hip_cuid_

	.text
	.amdgcn_target "amdgcn-amd-amdhsa--gfx1100"
	.protected	_Z10bfs_kernelPsPiS0_ys ; -- Begin function _Z10bfs_kernelPsPiS0_ys
	.globl	_Z10bfs_kernelPsPiS0_ys
	.p2align	8
	.type	_Z10bfs_kernelPsPiS0_ys,@function
_Z10bfs_kernelPsPiS0_ys:                ; @_Z10bfs_kernelPsPiS0_ys
; %bb.0:
	s_clause 0x1
	s_load_b32 s4, s[0:1], 0x34
	s_load_b64 s[2:3], s[0:1], 0x18
	s_waitcnt lgkmcnt(0)
	s_and_b32 s4, s4, 0xffff
	s_mul_i32 s3, s2, s3
	v_mad_u64_u32 v[1:2], null, s15, s4, v[0:1]
	s_mul_hi_u32 s4, s2, s2
	s_mul_i32 s2, s2, s2
	s_add_i32 s4, s4, s3
	s_delay_alu instid0(SALU_CYCLE_1) | instskip(NEXT) | instid1(VALU_DEP_1)
	s_add_i32 s3, s4, s3
	v_ashrrev_i32_e32 v2, 31, v1
	s_delay_alu instid0(VALU_DEP_1)
	v_cmp_gt_u64_e32 vcc_lo, s[2:3], v[1:2]
	s_and_saveexec_b32 s2, vcc_lo
	s_cbranch_execz .LBB0_6
; %bb.1:
	s_load_b128 s[4:7], s[0:1], 0x0
	v_lshlrev_b64 v[2:3], 1, v[1:2]
	s_load_b32 s0, s[0:1], 0x20
	s_waitcnt lgkmcnt(0)
	s_delay_alu instid0(VALU_DEP_1) | instskip(NEXT) | instid1(VALU_DEP_2)
	v_add_co_u32 v2, vcc_lo, s4, v2
	v_add_co_ci_u32_e32 v3, vcc_lo, s5, v3, vcc_lo
	global_load_u16 v0, v[2:3], off
	s_waitcnt vmcnt(0)
	v_cmp_eq_u16_e32 vcc_lo, s0, v0
	s_and_b32 exec_lo, exec_lo, vcc_lo
	s_cbranch_execz .LBB0_6
; %bb.2:
	s_mov_b32 s1, exec_lo
	s_brev_b32 s0, 1
.LBB0_3:                                ; %ComputeLoop
                                        ; =>This Inner Loop Header: Depth=1
	s_ctz_i32_b32 s2, s1
	s_delay_alu instid0(SALU_CYCLE_1) | instskip(SKIP_1) | instid1(SALU_CYCLE_1)
	v_readlane_b32 s3, v1, s2
	s_lshl_b32 s2, 1, s2
	s_and_not1_b32 s1, s1, s2
	s_delay_alu instid0(VALU_DEP_1)
	s_max_i32 s0, s0, s3
	s_cmp_lg_u32 s1, 0
	s_cbranch_scc1 .LBB0_3
; %bb.4:                                ; %ComputeEnd
	v_mbcnt_lo_u32_b32 v0, exec_lo, 0
	s_mov_b32 s1, exec_lo
	s_delay_alu instid0(VALU_DEP_1)
	v_cmpx_eq_u32_e32 0, v0
	s_xor_b32 s1, exec_lo, s1
	s_cbranch_execz .LBB0_6
; %bb.5:
	v_dual_mov_b32 v0, 0 :: v_dual_mov_b32 v1, s0
	global_atomic_max_i32 v0, v1, s[6:7]
.LBB0_6:
	s_nop 0
	s_sendmsg sendmsg(MSG_DEALLOC_VGPRS)
	s_endpgm
	.section	.rodata,"a",@progbits
	.p2align	6, 0x0
	.amdhsa_kernel _Z10bfs_kernelPsPiS0_ys
		.amdhsa_group_segment_fixed_size 0
		.amdhsa_private_segment_fixed_size 0
		.amdhsa_kernarg_size 296
		.amdhsa_user_sgpr_count 15
		.amdhsa_user_sgpr_dispatch_ptr 0
		.amdhsa_user_sgpr_queue_ptr 0
		.amdhsa_user_sgpr_kernarg_segment_ptr 1
		.amdhsa_user_sgpr_dispatch_id 0
		.amdhsa_user_sgpr_private_segment_size 0
		.amdhsa_wavefront_size32 1
		.amdhsa_uses_dynamic_stack 0
		.amdhsa_enable_private_segment 0
		.amdhsa_system_sgpr_workgroup_id_x 1
		.amdhsa_system_sgpr_workgroup_id_y 0
		.amdhsa_system_sgpr_workgroup_id_z 0
		.amdhsa_system_sgpr_workgroup_info 0
		.amdhsa_system_vgpr_workitem_id 0
		.amdhsa_next_free_vgpr 4
		.amdhsa_next_free_sgpr 16
		.amdhsa_float_round_mode_32 0
		.amdhsa_float_round_mode_16_64 0
		.amdhsa_float_denorm_mode_32 3
		.amdhsa_float_denorm_mode_16_64 3
		.amdhsa_dx10_clamp 1
		.amdhsa_ieee_mode 1
		.amdhsa_fp16_overflow 0
		.amdhsa_workgroup_processor_mode 1
		.amdhsa_memory_ordered 1
		.amdhsa_forward_progress 0
		.amdhsa_shared_vgpr_count 0
		.amdhsa_exception_fp_ieee_invalid_op 0
		.amdhsa_exception_fp_denorm_src 0
		.amdhsa_exception_fp_ieee_div_zero 0
		.amdhsa_exception_fp_ieee_overflow 0
		.amdhsa_exception_fp_ieee_underflow 0
		.amdhsa_exception_fp_ieee_inexact 0
		.amdhsa_exception_int_div_zero 0
	.end_amdhsa_kernel
	.text
.Lfunc_end0:
	.size	_Z10bfs_kernelPsPiS0_ys, .Lfunc_end0-_Z10bfs_kernelPsPiS0_ys
                                        ; -- End function
	.section	.AMDGPU.csdata,"",@progbits
; Kernel info:
; codeLenInByte = 256
; NumSgprs: 18
; NumVgprs: 4
; ScratchSize: 0
; MemoryBound: 0
; FloatMode: 240
; IeeeMode: 1
; LDSByteSize: 0 bytes/workgroup (compile time only)
; SGPRBlocks: 2
; VGPRBlocks: 0
; NumSGPRsForWavesPerEU: 18
; NumVGPRsForWavesPerEU: 4
; Occupancy: 16
; WaveLimiterHint : 0
; COMPUTE_PGM_RSRC2:SCRATCH_EN: 0
; COMPUTE_PGM_RSRC2:USER_SGPR: 15
; COMPUTE_PGM_RSRC2:TRAP_HANDLER: 0
; COMPUTE_PGM_RSRC2:TGID_X_EN: 1
; COMPUTE_PGM_RSRC2:TGID_Y_EN: 0
; COMPUTE_PGM_RSRC2:TGID_Z_EN: 0
; COMPUTE_PGM_RSRC2:TIDIG_COMP_CNT: 0
	.text
	.p2alignl 7, 3214868480
	.fill 96, 4, 3214868480
	.type	__hip_cuid_,@object             ; @__hip_cuid_
	.section	.bss,"aw",@nobits
	.globl	__hip_cuid_
__hip_cuid_:
	.byte	0                               ; 0x0
	.size	__hip_cuid_, 1

	.ident	"AMD clang version 18.0.0git (https://github.com/RadeonOpenCompute/llvm-project roc-6.3.2 25012 e5bf7e55c91490b07c49d8960fa7983d864936c4)"
	.section	".note.GNU-stack","",@progbits
	.addrsig
	.addrsig_sym __hip_cuid_
	.amdgpu_metadata
---
amdhsa.kernels:
  - .args:
      - .address_space:  global
        .offset:         0
        .size:           8
        .value_kind:     global_buffer
      - .address_space:  global
        .offset:         8
        .size:           8
        .value_kind:     global_buffer
      - .address_space:  global
        .offset:         16
        .size:           8
        .value_kind:     global_buffer
      - .offset:         24
        .size:           8
        .value_kind:     by_value
      - .offset:         32
        .size:           2
        .value_kind:     by_value
      - .offset:         40
        .size:           4
        .value_kind:     hidden_block_count_x
      - .offset:         44
        .size:           4
        .value_kind:     hidden_block_count_y
      - .offset:         48
        .size:           4
        .value_kind:     hidden_block_count_z
      - .offset:         52
        .size:           2
        .value_kind:     hidden_group_size_x
      - .offset:         54
        .size:           2
        .value_kind:     hidden_group_size_y
      - .offset:         56
        .size:           2
        .value_kind:     hidden_group_size_z
      - .offset:         58
        .size:           2
        .value_kind:     hidden_remainder_x
      - .offset:         60
        .size:           2
        .value_kind:     hidden_remainder_y
      - .offset:         62
        .size:           2
        .value_kind:     hidden_remainder_z
      - .offset:         80
        .size:           8
        .value_kind:     hidden_global_offset_x
      - .offset:         88
        .size:           8
        .value_kind:     hidden_global_offset_y
      - .offset:         96
        .size:           8
        .value_kind:     hidden_global_offset_z
      - .offset:         104
        .size:           2
        .value_kind:     hidden_grid_dims
    .group_segment_fixed_size: 0
    .kernarg_segment_align: 8
    .kernarg_segment_size: 296
    .language:       OpenCL C
    .language_version:
      - 2
      - 0
    .max_flat_workgroup_size: 1024
    .name:           _Z10bfs_kernelPsPiS0_ys
    .private_segment_fixed_size: 0
    .sgpr_count:     18
    .sgpr_spill_count: 0
    .symbol:         _Z10bfs_kernelPsPiS0_ys.kd
    .uniform_work_group_size: 1
    .uses_dynamic_stack: false
    .vgpr_count:     4
    .vgpr_spill_count: 0
    .wavefront_size: 32
    .workgroup_processor_mode: 1
amdhsa.target:   amdgcn-amd-amdhsa--gfx1100
amdhsa.version:
  - 1
  - 2
...

	.end_amdgpu_metadata
