Given a matrix with n rows and m columns. Your task is to find the kth element which is obtained while traversing the matrix spirally. You need to complete the method findK which takes four arguments the first argument is the matrix A and the next two arguments will be n and m denoting the size of the matrix A and then the forth argument is an integer k. The function will return the kth element obtained while traversing the matrix spirally.
Example 1:
Input:
n = 4, m = 4, k = 10
A[][] = {{1  2  3  4},
         {5  6  7  8},
         {9  10 11 12},
         {13 14 15 16}}
Output:
14
Explanation:
The spiral order of matrix will look like 1->2->3->4->8->12->16->15->14->13->9->5->6->7->11->10. So the 10th element in this order is 14. 
Example 2:
Input:
n = 3, m = 3, k = 4
A[][] = {{1 2 3},
         {4 5 6},
         {7 8 9}}
Output:
6
Explanation:
The spiral order of matrix will look like 1->2->3->6->9->8->7->4->5. So the 4th element in this order is 6.
Your Task:
You only need to implement the given function findK(). Do not read input, instead use the arguments given in the function. Return the K'th element obtained by traversing matrix spirally.
Expected Time Complexity: O(n*m)
Expected Auxiliary Space: O(n*m)
Constraints:
1<=n,m<=10^{3}
1<=k<=n*m

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3

class Solution:
    def findK(self, a, n, m, k):
        # Write Your Code here

Solutions:
def findK(arr, m, n, k):
	seen = [[0 for i in range(n)] for j in range(m)]
	dr = [0, 1, 0, -1]
	dc = [1, 0, -1, 0]
	x = 0
	y = 0
	di = 0
	b = 1
	for i in range(m * n):
		if b == k:
			return matrix[x][y]
		seen[x][y] = True
		cr = x + dr[di]
		cc = y + dc[di]
		if 0 <= cr and cr < m and (0 <= cc) and (cc < n) and (not seen[cr][cc]):
			x = cr
			y = cc
		else:
			di = (di + 1) % 4
			x += dr[di]
			y += dc[di]
		b += 1


def findK(arr, n, m, k):
	li = arr.pop(0)
	while len(arr):
		si = []
		for i in zip(*arr):
			si.append(list(i))
		arr = si[::-1]
		li += arr.pop(0)
	return li[k - 1]


def findK(arr, n, m, k):
	top = 0
	left = 0
	bottom = n - 1
	right = m - 1
	dir = 1
	find_count = 1
	while top <= bottom and right >= left:
		if dir == 1:
			for i in range(left, right + 1):
				if find_count == k:
					return arr[top][i]
				find_count += 1
			top += 1
			dir = 2
		elif dir == 2:
			for i in range(top, bottom + 1):
				if find_count == k:
					return arr[i][right]
				find_count += 1
			right -= 1
			dir = 3
		elif dir == 3:
			for i in range(right, left - 1, -1):
				if find_count == k:
					return arr[bottom][i]
				find_count += 1
			bottom -= 1
			dir = 4
		else:
			for i in range(bottom, top - 1, -1):
				if find_count == k:
					return arr[i][left]
				find_count += 1
			left += 1
			dir = 1
	return None


def findK(matrix, r, c, k):
	(left, right) = (0, c - 1)
	(top, bottom) = (0, r - 1)
	ans = []
	while left <= right and top <= bottom:
		for i in range(left, right + 1):
			ans.append(matrix[top][i])
		top += 1
		if top > bottom:
			break
		for i in range(top, bottom + 1):
			ans.append(matrix[i][right])
		right -= 1
		if left > right:
			break
		for i in range(right, left - 1, -1):
			ans.append(matrix[bottom][i])
		bottom -= 1
		if top > bottom:
			break
		for i in range(bottom, top - 1, -1):
			ans.append(matrix[i][left])
		left += 1
		if left > right:
			break
	return ans[k - 1]


def findK(arr, n, m, k):
	(top, left) = (0, 0)
	(bottom, right) = (n - 1, m - 1)
	ans = []
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			ans.append(matrix[top][i])
		top += 1
		for i in range(top, bottom + 1):
			ans.append(matrix[i][right])
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				ans.append(matrix[bottom][i])
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				ans.append(matrix[i][left])
			left += 1
	return ans[k - 1]


def findK(a, n, m, k):
	val = 1
	(left, right) = (0, len(a[0]) - 1)
	(top, bottom) = (0, len(a) - 1)
	while left <= right and top <= bottom:
		for c in range(left, right + 1):
			if val == k:
				return a[top][c]
			val += 1
		top += 1
		for r in range(top, bottom + 1):
			if val == k:
				return a[r][right]
			val += 1
		right -= 1
		for c in range(right, left - 1, -1):
			if val == k:
				return a[bottom][c]
			val += 1
		bottom -= 1
		for r in range(bottom, top - 1, -1):
			if val == k:
				return a[r][left]
			val += 1
		left += 1


def findK(mat, n, m, k):
	ans = []
	left = 0
	right = m
	top = 0
	bot = n
	num = 1
	while left < right and top < bot:
		for i in range(left, right, 1):
			ans.append(mat[top][i])
		top += 1
		for i in range(top, bot, 1):
			ans.append(mat[i][right - 1])
		right -= 1
		if top < bot:
			for i in range(right - 1, left - 1, -1):
				ans.append(mat[bot - 1][i])
		bot -= 1
		if left < right:
			for i in range(bot - 1, top - 1, -1):
				ans.append(mat[i][left])
		left += 1
	return ans[k - 1]


def findK(a, n, m, k):
	start_row = 0
	start_col = 0
	end_row = n - 1
	end_col = m - 1
	t = 1
	while start_row <= end_row and start_col <= end_col:
		for i in range(start_col, end_col + 1):
			if t == k:
				return a[start_row][i]
			t += 1
		start_row += 1
		for i in range(start_row, end_row + 1):
			if t == k:
				return a[i][end_col]
			t += 1
		end_col -= 1
		if start_col <= end_col:
			for i in range(end_col, start_col - 1, -1):
				if t == k:
					return a[end_row][i]
				t += 1
			end_row -= 1
		if start_row <= end_row:
			for i in range(end_row, start_row - 1, -1):
				if t == k:
					return a[i][start_col]
				t += 1
			start_col += 1


def findK(arr, n, m, k):
	left = 0
	right = m - 1
	top = 0
	bottom = n - 1
	count = k
	while left <= right and top <= bottom:
		for i in range(left, right + 1):
			count -= 1
			if count == 0:
				return arr[top][i]
		top += 1
		if top <= bottom:
			for i in range(top, bottom + 1):
				count -= 1
				if count == 0:
					return arr[i][right]
		right -= 1
		if left <= right and top <= bottom:
			for i in range(right, left - 1, -1):
				count -= 1
				if count == 0:
					return arr[bottom][i]
		bottom -= 1
		if left <= right and top <= bottom:
			for i in range(bottom, top - 1, -1):
				count -= 1
				if count == 0:
					return arr[i][left]
		left += 1


def findK(arr, n, m, k):
	ans = []

	def printdata(arr, i, j, m, n):
		if i >= m or j >= n:
			return
		for p in range(i, n):
			ans.append(arr[i][p])
		for p in range(i + 1, m):
			ans.append(arr[p][n - 1])
		if m - 1 != i:
			for p in range(n - 2, j - 1, -1):
				ans.append(arr[m - 1][p])
		if n - 1 != j:
			for p in range(m - 2, i, -1):
				ans.append(arr[p][j])
		printdata(arr, i + 1, j + 1, m - 1, n - 1)
	printdata(arr, 0, 0, n, m)
	return ans[k - 1]


def findK(matrix, n, m, k):
	l = 0
	r = m - 1
	u = 0
	d = n - 1
	i = 0
	res = []
	k -= 1
	while l <= r and u <= d:
		for i in range(l, r + 1):
			if k == 0:
				return matrix[u][i]
			k -= 1
		u += 1
		for i in range(u, d + 1):
			if k == 0:
				return matrix[i][r]
			k -= 1
		r -= 1
		for i in range(r, l - 1, -1):
			if k == 0:
				return matrix[d][i]
			k -= 1
		d -= 1
		for i in range(d, u - 1, -1):
			if k == 0:
				return matrix[i][l]
			k -= 1
		l += 1
	return -1


def findK(arr, n, m, k):
	(x, y) = (0, 0)
	dx = [0, 1, 0, -1]
	dy = [1, 0, -1, 0]
	dr = 0
	(min_c, max_c) = (0, m - 1)
	(min_r, max_r) = (0, n - 1)
	while k > 0:
		k -= 1
		if k == 0:
			return arr[x][y]
		if x + dx[dr] > max_r:
			dr = (dr + 1) % 4
			max_c -= 1
		elif x + dx[dr] < min_r:
			dr = (dr + 1) % 4
			min_c += 1
		elif y + dy[dr] > max_c:
			dr = (dr + 1) % 4
			min_r += 1
		elif y + dy[dr] < min_c:
			dr = (dr + 1) % 4
			max_r -= 1
		x += dx[dr]
		y += dy[dr]
	return -1


def func(pos, arr, visted, ans):
	(i, j, up) = pos
	if 0 <= i < len(arr) and 0 <= j < len(arr[0]) and ((i, j) not in visted):
		visted.add((i, j))
		ans.append(arr[i][j])
		if up:
			func((i - 1, j, True), arr, visted, ans)
		func((i, j + 1, False), arr, visted, ans)
		func((i + 1, j, False), arr, visted, ans)
		func((i, j - 1, False), arr, visted, ans)
		func((i - 1, j, True), arr, visted, ans)

def findK(arr, n, m, k):
	ans = []
	visted = set()
	func((0, 0, False), arr, visted, ans)
	return ans[k - 1]


def findK(arr, n, m, k):
	traverse = []
	l = 0
	r = m - 1
	u = 0
	d = n - 1
	while l <= r and u <= d:
		for i in range(l, r + 1):
			traverse.append(matrix[u][i])
		u += 1
		for i in range(u, d + 1):
			traverse.append(matrix[i][r])
		r -= 1
		for i in range(r, l - 1, -1):
			traverse.append(matrix[d][i])
		d -= 1
		for i in range(d, u - 1, -1):
			traverse.append(matrix[i][l])
		l += 1
	return traverse[k - 1]


def findK(arr, r, c, k):
	t = 0
	l = 0
	m = r
	n = c
	li = []
	count = 0
	while t < m and l < n:
		for i in range(l, n):
			li.append(matrix[t][i])
			count += 1
		if count >= k:
			break
		t += 1
		for i in range(t, m):
			li.append(matrix[i][n - 1])
			count += 1
		if count >= k:
			break
		n -= 1
		if t < m:
			for i in range(n - 1, l - 1, -1):
				li.append(matrix[m - 1][i])
				count += 1
		if count >= k:
			break
		m -= 1
		if l < n:
			for i in range(m - 1, t - 1, -1):
				li.append(matrix[i][l])
				count += 1
			l += 1
		if count >= k:
			break
	return li[k - 1]


def findK(arr, n, m, k):
	(r, l) = (m - 1, 0)
	(d, t) = (n - 1, 0)
	ans = []
	dir = 0
	while l <= r and t <= d:
		if dir == 0:
			for i in range(l, r + 1):
				ans.append(matrix[t][i])
			t += 1
		if dir == 1:
			for i in range(t, d + 1):
				ans.append(matrix[i][r])
			r -= 1
		if dir == 2:
			for i in range(r, l - 1, -1):
				ans.append(matrix[d][i])
			d -= 1
		if dir == 3:
			for i in range(d, t - 1, -1):
				ans.append(matrix[i][l])
			l += 1
		dir = (dir + 1) % 4
	return ans[k - 1]


def findK(arr, n, m, k):
	top = 0
	bottom = n - 1
	left = 0
	right = m - 1
	dir = 0
	res = []
	while top <= bottom and left <= right:
		if dir == 0:
			for j in range(left, right + 1):
				res.append(arr[top][j])
			top += 1
		if dir == 1:
			for i in range(top, bottom + 1):
				res.append(arr[i][right])
			right -= 1
		if dir == 2:
			for j in range(right, left - 1, -1):
				res.append(arr[bottom][j])
			bottom -= 1
		if dir == 3:
			for i in range(bottom, top - 1, -1):
				res.append(arr[i][left])
			left += 1
		dir = (dir + 1) % 4
	return res[k - 1]


def findK(arr, n, m, k):
	top = 0
	bottom = n - 1
	left = 0
	right = m - 1
	dir = 0
	result = 0
	while top <= bottom and left <= right:
		if dir == 0:
			for i in range(left, right + 1):
				k -= 1
				if k == 0:
					result = arr[top][i]
					break
			top += 1
			dir = 1
		elif dir == 1:
			for i in range(top, bottom + 1):
				k -= 1
				if k == 0:
					result = arr[i][right]
					break
			right -= 1
			dir = 2
		elif dir == 2:
			for i in range(right, left - 1, -1):
				k -= 1
				if k == 0:
					result = arr[bottom][i]
					break
			bottom -= 1
			dir = 3
		elif dir == 3:
			for i in range(bottom, top - 1, -1):
				k -= 1
				if k == 0:
					result = arr[i][left]
					break
			left += 1
			dir = 0
	return result


def findK(arr, n, m, k):
	count = n * m
	ind = 1
	cols = 0
	cole = m
	rows = 0
	rowe = n
	ele = -1
	z = True
	while ind < count and z == True:
		i = cols
		while i < cole and z:
			if k == 1:
				ele = arr[rows][i]
				z = False
				break
			k -= 1
			ind += 1
			i += 1
		rows += 1
		i = rows
		while i < rowe and z:
			if k == 1:
				ele = arr[i][cole - 1]
				z = False
				break
			k -= 1
			i += 1
			ind += 1
		cole -= 1
		i = cole - 1
		while i >= cols and z:
			if k == 1:
				ele = arr[rowe - 1][i]
				z = False
				break
			k -= 1
			i -= 1
			ind += 1
		rowe -= 1
		i = rowe - 1
		while i >= rows and z:
			if k == 1:
				ele = arr[i][cols]
				z = False
				break
			k -= 1
			i -= 1
			ind += 1
		rowe -= 1
	return ele


def findK(arr, n, m, k):
	spiral = []
	j = 0
	while len(spiral) < k:
		for i in range(j, m - j):
			spiral.append(arr[j][i])
		for i in range(j + 1, n - j - 1):
			spiral.append(arr[i][-j - 1])
		for i in range(j, m - j):
			spiral.append(arr[-j - 1][-i - 1])
		for i in range(j + 1, n - j - 1):
			spiral.append(arr[-i - 1][j])
		j += 1
	return spiral[k - 1]


def findK(nums, n, m, k):
	l1 = []
	c = 0
	t = 0
	b = n - 1
	l = 0
	r = m - 1
	while t <= b and l <= r:
		if c == 0:
			for i in range(l, r + 1):
				l1.append(nums[t][i])
			t += 1
		if c == 1:
			for i in range(t, b + 1):
				l1.append(nums[i][r])
			r -= 1
		if c == 2:
			for i in range(r, l - 1, -1):
				l1.append(nums[b][i])
			b -= 1
		if c == 3:
			for i in range(b, t - 1, -1):
				l1.append(nums[i][l])
			l += 1
		c = (c + 1) % 4
	return l1[k - 1]


def findK(arr, n, m, k):
	rs = 0
	re = n
	cs = 0
	ce = m
	if n * m < k:
		return -1
	while rs < re and cs < ce:
		for i in range(cs, ce):
			k -= 1
			if k == 0:
				return arr[rs][i]
		rs += 1
		for i in range(rs, re):
			k -= 1
			if k == 0:
				return arr[i][ce - 1]
		ce -= 1
		if rs < re:
			for i in range(ce - 1, cs - 1, -1):
				k -= 1
				if k == 0:
					return arr[re - 1][i]
		re -= 1
		if cs < ce:
			for i in range(re - 1, rs - 1, -1):
				k -= 1
				if k == 0:
					return arr[i][cs]
		cs -= 1
	return -1


def findK(A, n, m, k):
	count = 1
	rs = 0
	re = n - 1
	cs = 0
	ce = m - 1
	while rs <= re and cs <= ce and (count <= n * m):
		for c in range(cs, ce + 1):
			if count == k:
				return A[rs][c]
			count += 1
		rs += 1
		for r in range(rs, re + 1):
			if count == k:
				return A[r][ce]
			count += 1
		ce -= 1
		for c in range(ce, cs - 1, -1):
			if count == k:
				return A[re][c]
			count += 1
		re -= 1
		for r in range(re, rs - 1, -1):
			if count == k:
				return A[r][cs]
			count += 1


def findK(arr, n, m, k):
	left = 0
	right = m - 1
	top = 0
	bottom = n - 1
	direction = 0
	c = 0
	while left <= right and top <= bottom:
		if direction == 0:
			for i in range(left, right + 1):
				c += 1
				if c == k:
					return arr[top][i]
			top += 1
		elif direction == 1:
			for i in range(top, bottom + 1):
				c += 1
				if c == k:
					return arr[i][right]
			right -= 1
		elif direction == 2:
			for i in range(right, left - 1, -1):
				c += 1
				if c == k:
					return arr[bottom][i]
			bottom -= 1
		elif direction == 3:
			for i in range(bottom, top - 1, -1):
				c += 1
				if c == k:
					return arr[i][left]
			left += 1
		direction = (direction + 1) % 4


def findK(arr, n, m, k):
	if not matrix:
		return
	res = []
	while matrix:
		if matrix:
			res.extend(matrix.pop(0))
		if matrix and matrix[0]:
			for row in matrix:
				res.append(row.pop())
		if matrix:
			res.extend(matrix.pop()[::-1])
		if matrix and matrix[0]:
			res.extend([row.pop(0) for row in matrix][::-1])
	return res[k - 1]


def findK(arr, n, m, ind):
	k = 0
	l = 0
	ans = []
	while k < n and l < m:
		for i in range(l, m):
			ans.append(arr[k][i])
		k += 1
		for i in range(k, n):
			ans.append(arr[i][m - 1])
		m -= 1
		if k < n:
			for i in range(m - 1, l - 1, -1):
				ans.append(arr[n - 1][i])
			n -= 1
		if l < m:
			for i in range(n - 1, k - 1, -1):
				ans.append(arr[i][l])
			l += 1
	return ans[ind - 1]


def findK(arr, n, m, k):
	f = m * n
	(r, c) = (0, 0)
	i = 0
	u = -1
	l = [0 for a in range(m * n)]
	while True:
		for c in range(r, m):
			l[i] = matrix[r][c]
			i += 1
		if i == f:
			break
		for r in range(r + 1, n):
			l[i] = matrix[r][c]
			i += 1
		if i == f:
			break
		for c in range(c - 1, u, -1):
			l[i] = matrix[r][c]
			i = i + 1
		if i == f:
			break
		for r in range(r - 1, c, -1):
			l[i] = matrix[r][c]
			i = i + 1
		if i == f:
			break
		m = m - 1
		n = n - 1
		c = c + 1
		u = u + 1
	return l[k - 1]


def findK(arr, n, m, k):
	(row_start, col_start) = (0, 0)
	count = 0
	(r, c) = (n, m)
	while row_start < r and col_start < c:
		for i in range(col_start, c):
			count += 1
			if count == k:
				return matrix[row_start][i]
		row_start += 1
		for i in range(row_start, r):
			count += 1
			if count == k:
				return matrix[i][c - 1]
		c -= 1
		if row_start < r:
			for i in range(c - 1, col_start - 1, -1):
				count += 1
				if count == k:
					return matrix[r - 1][i]
			r -= 1
		if col_start < c:
			for i in range(r - 1, row_start - 1, -1):
				count += 1
				if count == k:
					return matrix[i][col_start]
			col_start += 1
	return 0


def findK(arr, n, m, k):
	li = []
	if len(arr) == 0:
		return
	kr = 0
	lc = 0
	nr = len(arr)
	mc = len(arr[0])
	while kr < nr and lc < mc:
		for i in range(lc, mc):
			li.append(arr[kr][i])
		kr += 1
		for j in range(kr, nr):
			li.append(arr[j][mc - 1])
		mc -= 1
		if kr < nr:
			for i in range(mc - 1, lc - 1, -1):
				li.append(arr[nr - 1][i])
			nr -= 1
		if lc < mc:
			for j in range(nr - 1, kr - 1, -1):
				li.append(arr[j][lc])
			lc += 1
	for i in range(len(li)):
		if i == k - 1:
			return li[i]
	return -1


def findK(m, r, c, k):
	(i, j) = (0, 0)
	while k >= 2 * (r + c - 2):
		if k == 2 * (r + c - 2):
			return m[i + 1][j]
		i += 1
		j += 1
		k -= 2 * (r + c - 2)
		r -= 2
		c -= 2
	if k <= c:
		return m[i][j + k - 1]
	elif k <= c + r - 1:
		return m[i + k - c][j + c - 1]
	elif k <= 2 * c + r - 2:
		return m[i + r - 1][j + c - 1 - (k - c - r + 1)]
	else:
		return m[i + r - 1 - (k - 2 * c - r + 2)][j]


def findK(arr, n, m, k):
	x = n
	y = m
	c = 0
	cnt = 1
	prv = 0
	for i in range(n * m):
		if x <= 0 or y <= 0 or 2 * y < 4:
			break
		else:
			prv = c
			c = c + (2 * x + (2 * y - 4))
			if k <= c:
				break
			else:
				cnt += 1
				x -= 2
				y -= 2
	if c < k:
		prv = c
	i = cnt - 1
	j = cnt - 1
	prv += 1
	for i in range(cnt - 1, cnt - 1 + y):
		if prv == k:
			return arr[cnt - 1][i]
		else:
			prv += 1
	for j in range(cnt, cnt + x - 1):
		if prv == k:
			return arr[j][i]
		else:
			prv += 1
	xx = i - 1
	for i in range(xx, cnt - 1 - 1, -1):
		if prv == k:
			return arr[j][i]
		else:
			prv += 1
	yy = j - 1
	for j in range(yy, cnt, -1):
		if prv == k:
			return arr[j][i]
		else:
			prv += 1


def findK(arr, n, m, k):
	result = []
	row_start = 0
	row_end = n - 1
	col_start = 0
	col_end = m - 1
	while col_start <= col_end and row_start <= row_end:
		i = col_start
		while i <= col_end:
			result.append(matrix[row_start][i])
			i += 1
		row_start += 1
		i = row_start
		while i <= row_end:
			result.append(matrix[i][col_end])
			i += 1
		col_end -= 1
		if col_start > col_end or row_start > row_end:
			break
		i = col_end
		while i >= col_start:
			result.append(matrix[row_end][i])
			i -= 1
		row_end -= 1
		i = row_end
		while i >= row_start:
			result.append(matrix[i][col_start])
			i -= 1
		col_start += 1
	return result[k - 1]


def findK(A, R, C, K):
	(top, down) = (0, R - 1)
	(left, right) = (0, C - 1)
	while top <= down and left <= right:
		for j in range(left, right + 1):
			K -= 1
			if K == 0:
				return A[top][j]
		top += 1
		for i in range(top, down + 1):
			K -= 1
			if K == 0:
				return A[i][right]
		right -= 1
		for j in range(right, left - 1, -1):
			K -= 1
			if K == 0:
				return A[down][j]
		down -= 1
		for i in range(down, top - 1, -1):
			K -= 1
			if K == 0:
				return A[i][left]
		left += 1


def findK(arr, n, m, k):
	row_st = 0
	col_st = 0
	row_end = n - 1
	col_end = m - 1
	maxi = n * m
	count = 0
	ls = []
	while row_st <= row_end and col_st <= col_end:
		if count < maxi:
			for i in range(col_st, col_end + 1):
				ls.append(arr[row_st][i])
				count += 1
		row_st += 1
		if count < maxi:
			for i in range(row_st, row_end + 1):
				ls.append(arr[i][col_end])
				count += 1
		col_end -= 1
		if count < maxi:
			for i in range(col_end, col_st - 1, -1):
				ls.append(arr[row_end][i])
				count += 1
		row_end -= 1
		if count < maxi:
			for i in range(row_end, row_st - 1, -1):
				ls.append(arr[i][col_st])
				count += 1
		col_st += 1
	return ls[k - 1]


def findK(arr, n, m, k):
	row = 0
	col = 0
	c = []
	while row < n and col < m:
		for i in range(col, m):
			c.append(arr[row][i])
		row += 1
		for i in range(row, n):
			c.append(arr[i][m - 1])
		m -= 1
		if row < n:
			for i in range(m - 1, col - 1, -1):
				c.append(arr[n - 1][i])
			n -= 1
		if col < m:
			for i in range(n - 1, row - 1, -1):
				c.append(arr[i][col])
			col += 1
		return c[k - 1]


def findK(matrix, n, m, k):
	res = []
	top = 0
	bottom = len(matrix)
	left = 0
	right = len(matrix[0])
	while top < bottom and left < right:
		for i in range(left, right):
			res.append(matrix[top][i])
		top = top + 1
		for i in range(top, bottom):
			res.append(matrix[i][right - 1])
		right = right - 1
		if not (left < right and top < bottom):
			break
		for i in range(right - 1, left - 1, -1):
			res.append(matrix[bottom - 1][i])
		bottom = bottom - 1
		for i in range(bottom - 1, top - 1, -1):
			res.append(matrix[i][left])
		left = left + 1
	return res[k - 1]


def findK(array, R, C, k):
	(top, bottom) = (0, R - 1)
	(left, right) = (0, C - 1)
	result = []
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			result.append(matrix[top][i])
			if len(result) == k:
				return result[k - 1]
		top += 1
		for i in range(top, bottom + 1):
			result.append(matrix[i][right])
			if len(result) == k:
				return result[k - 1]
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				result.append(matrix[bottom][i])
				if len(result) == k:
					return result[k - 1]
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				result.append(matrix[i][left])
			left += 1
	return -1


def findK(arr, n, m, k):
	res = []
	while arr:
		res.extend(arr.pop(0))
		arr = list(zip(*arr))[::-1]
	return res[k - 1]


def findK(arr, n, m, k):
	r = 0
	c = 0
	count = 0
	sr = 0
	sc = 0
	er = n - 1
	ec = m - 1
	while sr <= er and sc <= ec:
		while c < ec:
			count += 1
			if count == k:
				return arr[r][c]
			c += 1
		sr += 1
		while r < er:
			count += 1
			if count == k:
				return arr[r][c]
			r += 1
		ec -= 1
		while c > sc:
			count += 1
			if count == k:
				return arr[r][c]
			c -= 1
		er -= 1
		while r > sr:
			count += 1
			if count == k:
				return arr[r][c]
			r -= 1
		sc += 1
	return -1


def findK(arr, n, m, k):
	top = 0
	bottom = n - 1
	left = 0
	right = m - 1
	res = []
	while left <= right and top <= bottom:
		for i in range(left, right + 1):
			res.append(matrix[top][i])
		top += 1
		for j in range(top, bottom + 1):
			res.append(matrix[j][right])
		right -= 1
		if top <= bottom:
			for m in range(right, left - 1, -1):
				res.append(matrix[bottom][m])
			bottom -= 1
		if left <= right:
			for l in range(bottom, top - 1, -1):
				res.append(matrix[l][left])
			left += 1
	return res[k - 1]


def findK(arr, n, m, k):
	ibound = [0, n - 1]
	jbound = [0, m - 1]
	i = 0
	j = 0
	row = True
	right = True
	col = False
	down = False
	while k != 1:
		if row and right:
			if j == jbound[1]:
				row = False
				right = False
				col = True
				down = True
				i = +1
				ibound[0] += 1
			else:
				j += 1
		elif row and (not right):
			if j == jbound[0]:
				row = False
				right = False
				col = True
				down = False
				i -= 1
				ibound[1] -= 1
			else:
				j -= 1
		elif col and down:
			if i == ibound[1]:
				row = True
				right = False
				col = False
				down = False
				j -= 1
				jbound[1] -= 1
			else:
				i += 1
		elif col and (not down):
			if i == ibound[0]:
				row = True
				right = True
				col = False
				down = False
				j = +1
				jbound[0] += 1
			else:
				i -= 1
		k = k - 1
	return arr[i][j]


def findK(arr, n, m, k):
	(total, count1) = (n * m, 0)
	startingRow = 0
	startingCol = 0
	endingRow = n - 1
	endingCol = m - 1
	count = 1
	while count1 < total:
		for i in range(startingCol, endingCol + 1):
			if count == k:
				return arr[startingRow][i]
			count += 1
			count1 += 1
			if count1 > total:
				break
		startingRow += 1
		for i in range(startingRow, endingRow + 1):
			if count == k:
				return arr[i][endingCol]
			count += 1
			count1 += 1
			if count1 > total:
				break
		endingCol -= 1
		for i in range(endingCol, startingCol - 1, -1):
			if count == k:
				return arr[endingRow][i]
			count += 1
			count1 += 1
			if count1 > total:
				break
		endingRow -= 1
		for i in range(endingRow, startingRow - 1, -1):
			if count == k:
				return arr[i][startingCol]
			count += 1
			count1 += 1
			if count1 > total:
				break
		startingCol += 1


def findK(arr, n, m, k):
	(top, left, down, right) = (0, 0, n - 1, m - 1)
	arr = []
	ind = 1
	while left <= right and top <= down:
		for i in range(left, right + 1):
			arr.append(matrix[top][i])
			if ind == k:
				return arr[-1]
			ind += 1
		top += 1
		for i in range(top, down + 1):
			arr.append(matrix[i][right])
			if ind == k:
				return arr[-1]
			ind += 1
		right -= 1
		if left > right or top > down:
			break
		for i in range(right, left - 1, -1):
			arr.append(matrix[down][i])
			if ind == k:
				return arr[-1]
			ind += 1
		down -= 1
		for i in range(down, top - 1, -1):
			arr.append(matrix[i][left])
			if ind == k:
				return arr[-1]
			ind += 1
		left += 1
	return arr[-1]


def findK(arr, n, m, k):
	t = 0
	d = n - 1
	l = 0
	r = m - 1
	p = 0
	a = []
	while t <= d and l <= r:
		if p == 0:
			for i in range(l, r + 1):
				a.append(arr[t][i])
			t += 1
		elif p == 1:
			for i in range(t, d + 1):
				a.append(arr[i][r])
			r -= 1
		elif p == 2:
			for i in range(r, l - 1, -1):
				a.append(arr[d][i])
			d -= 1
		else:
			for i in range(d, t - 1, -1):
				a.append(arr[i][l])
			l += 1
		p = (p + 1) % 4
	return a[k - 1]


def findK(arr, n, m, k):
	lst = []
	l = top = 0
	r = len(arr[0]) - 1
	bottom = len(arr) - 1
	while l <= r and top <= bottom:
		for i in range(l, r + 1):
			lst.append(arr[top][i])
		top += 1
		for i in range(top, bottom + 1):
			lst.append(arr[i][r])
		r -= 1
		if top <= bottom:
			for i in range(r, l - 1, -1):
				lst.append(arr[bottom][i])
			bottom -= 1
		if l <= r:
			for i in range(bottom, top - 1, -1):
				lst.append(arr[i][l])
			l += 1
	return lst[k - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		matrix = [[0 for i in range(n[1])] for j in range(n[0])]
		c = 0
		for i in range(n[0]):
			for j in range(n[1]):
				matrix[i][j] = arr[c]
				c += 1
		print(findK(matrix, n[0], n[1], n[2]))


def findK(arr, n, m, k):
	(r, c) = (len(arr), len(arr[0]))
	(left, right, top, bottom) = (0, c - 1, 0, r - 1)
	(ans, idx) = (0, 0)
	while left <= right and top <= bottom:
		for i in range(left, right + 1):
			ans += 1
			if ans == k:
				idx = arr[top][i]
				break
		top += 1
		for i in range(top, bottom + 1):
			ans += 1
			if ans == k:
				idx = arr[i][right]
				break
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				ans += 1
				if ans == k:
					idx = arr[bottom][i]
					break
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				ans += 1
				if ans == k:
					idx = arr[i][left]
					break
			left += 1
	return idx
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		matrix = [[0 for i in range(n[1])] for j in range(n[0])]
		c = 0
		for i in range(n[0]):
			for j in range(n[1]):
				matrix[i][j] = arr[c]
				c += 1
		print(findK(matrix, n[0], n[1], n[2]))


def findK(arr, n, m, k):

	def bound(matrix, r, c):
		ans = []
		if r > 0 and c > 0:
			try:
				for ele in matrix[0][:]:
					ans.append(ele)
			except:
				pass
			try:
				for ele in matrix[1:r - 1]:
					ans.append(ele[c - 1])
			except:
				pass
			try:
				for ele in matrix[r - 1][:][::-1]:
					ans.append(ele)
			except:
				pass
			try:
				for ele in matrix[1:r - 1][::-1]:
					ans.append(ele[0])
			except:
				pass
			a = []
			for li in matrix[1:r - 1]:
				a.append(li[1:c - 1])
			return ans + bound(a, r - 2, c - 2)[:]
		else:
			return ans
	res = bound(arr, n, m)
	return res[:n * m][k - 1]
if __name__ == '__main__':
	t = int(input())
	for i in range(t):
		n = list(map(int, input().strip().split()))
		arr = list(map(int, input().strip().split()))
		matrix = [[0 for i in range(n[1])] for j in range(n[0])]
		c = 0
		for i in range(n[0]):
			for j in range(n[1]):
				matrix[i][j] = arr[c]
				c += 1
		print(findK(matrix, n[0], n[1], n[2]))


def findK(a, n, m, k):
	if n < 1 or m < 1:
		return -1
	if k <= m:
		return a[0][k - 1]
	if k <= m + n - 1:
		return a[k - m][m - 1]
	if k <= m + n - 1 + m - 1:
		return a[n - 1][m - 1 - (k - (m + n - 1))]
	if k <= m + n - 1 + m - 1 + n - 2:
		return a[n - 1 - (k - (m + n - 1 + m - 1))][0]
	a.pop(0)
	for j in a:
		j.pop(0)
	return findK(a, n - 2, m - 2, k - (2 * n + 2 * m - 4))


def findK(arr, n, m, k):
	frow = 0
	fcol = 0
	lrow = n - 1
	lcol = m - 1
	cnt = 0
	while True:
		for i in range(fcol, lcol + 1):
			cnt += 1
			if cnt == k:
				return arr[frow][i]
		frow += 1
		for i in range(frow, lrow + 1):
			cnt += 1
			if cnt == k:
				return arr[i][lcol]
		lcol -= 1
		for i in range(lcol, fcol - 1, -1):
			cnt += 1
			if cnt == k:
				return arr[lrow][i]
		lrow -= 1
		for i in range(lrow, frow - 1, -1):
			cnt += 1
			if cnt == k:
				return arr[i][fcol]
		fcol += 1


def findK(arr, n, m, k):
	l = []
	i = 0
	j = 0
	a = k
	while i < n and j < m:
		for k in range(j, m):
			l.append(arr[i][k])
		i += 1
		for k in range(i, n):
			l.append(arr[k][m - 1])
		m -= 1
		for k in range(m - 1, j - 1, -1):
			l.append(arr[n - 1][k])
		n -= 1
		for k in range(n - 1, i - 1, -1):
			l.append(arr[k][j])
		j += 1
	return l[a - 1]


def findK(matrix, r, c, tar):
	k = 0
	while r > k and c > k:
		for j in range(k, c):
			tar -= 1
			if tar == 0:
				return matrix[k][j]
		for i in range(k + 1, r):
			tar -= 1
			if tar == 0:
				return matrix[i][c - 1]
		j = c - 2
		while k >= k and r != k + 1:
			tar -= 1
			if tar == 0:
				return matrix[r - 1][j]
			j -= 1
		i = r - 2
		while i > k and c != k + 1:
			tar -= 1
			if tar == 0:
				return matrix[i][k]
			i -= 1
		r -= 1
		c -= 1
		k += 1
	return -1


def findK(arr, n, m, k):
	di = 0
	top = 0
	bottom = n - 1
	left = 0
	right = m - 1
	c = []
	d = 0
	while top <= bottom and left <= right:
		if di == 0:
			for i in range(left, right + 1):
				c.append(arr[top][i])
				d = d + 1
			top += 1
		if di == 1:
			for i in range(top, bottom + 1):
				c.append(arr[i][right])
				d = d + 1
			right -= 1
		if di == 2:
			for i in range(right, left - 1, -1):
				c.append(arr[bottom][i])
				d = d + 1
			bottom -= 1
		if di == 3:
			for i in range(bottom, top - 1, -1):
				c.append(arr[i][left])
				d = d + 1
			left += 1
		di = (di + 1) % 4
	return c[k - 1]


def findK(arr, n, m, k):
	top = 0
	down = n - 1
	left = 0
	right = m - 1
	l = []
	dirc = 0
	while top <= down and left <= right:
		if dirc == 0:
			for i in range(left, right + 1):
				l.append(matrix[top][i])
			top += 1
		elif dirc == 1:
			for i in range(top, down + 1):
				l.append(matrix[i][right])
			right -= 1
		elif dirc == 2:
			for i in reversed(range(left, right + 1)):
				l.append(matrix[down][i])
			down -= 1
		elif dirc == 3:
			for i in reversed(range(top, down + 1)):
				l.append(matrix[i][left])
			left += 1
		dirc = (dirc + 1) % 4
	return l[k - 1]


def findK(arr, n, m, k):
	rowbegin = 0
	colbegin = 0
	rowend = n - 1
	colend = m - 1
	res = []
	while rowbegin <= rowend and colbegin <= colend:
		for i in range(colbegin, colend + 1):
			res.append(arr[rowbegin][i])
		rowbegin += 1
		for i in range(rowbegin, rowend + 1):
			res.append(arr[i][colend])
		colend -= 1
		if rowbegin <= rowend:
			for i in range(colend, colbegin - 1, -1):
				res.append(arr[rowend][i])
			rowend -= 1
		if colbegin <= colend:
			for i in range(rowend, rowbegin - 1, -1):
				res.append(arr[i][colbegin])
			colbegin += 1
	return res[k - 1]


def findK(arr, row, col, k):
	res = []
	top = 0
	bottom = row - 1
	left = 0
	right = col - 1
	if row == 1:
		return arr[row - 1][k - 1]
	if col == 1:
		return arr[k - 1][col - 1]
	while top < bottom and left < right:
		for i in range(left, right + 1):
			res.append(arr[top][i])
		for i in range(top + 1, bottom + 1):
			res.append(arr[i][right])
		for i in range(right - 1, left - 1, -1):
			res.append(arr[bottom][i])
		for i in range(bottom - 1, top, -1):
			res.append(arr[i][left])
		top += 1
		bottom -= 1
		left += 1
		right -= 1
	return res[k - 1]


import math

def findK(arr, n, m, k):
	for i in range(math.ceil(n / 2)):
		for j in range(i, m - i):
			k -= 1
			if k == 0:
				return arr[i][j]
		for j in range(i + 1, n - i - 1):
			k -= 1
			if k == 0:
				return arr[j][m - i - 1]
		for j in range(m - i - 1, i - 1, -1):
			k -= 1
			if k == 0:
				return arr[n - i - 1][j]
		for j in range(n - i - 2, i, -1):
			k -= 1
			if k == 0:
				return arr[j][i]


def findK(arr, n, m, k):
	top = 0
	down = n - 1
	left = 0
	right = m - 1
	d = 0
	k1 = 1
	while top <= down and left <= right:
		if d == 0:
			for i in range(left, right + 1):
				if k1 == k:
					return arr[top][i]
				k1 += 1
			top += 1
		if d == 1:
			for i in range(top, down + 1):
				if k1 == k:
					return arr[i][right]
				k1 += 1
			right -= 1
		if d == 2:
			for i in range(right, left - 1, -1):
				if k1 == k:
					return arr[down][i]
				k1 += 1
			down -= 1
		if d == 3:
			for i in range(down, top - 1, -1):
				if k1 == k:
					return arr[i][left]
				k1 += 1
			left += 1
		d = (d + 1) % 4


def findK(arr, n, m, k):
	l = list()
	t = 0
	r1 = m - 1
	b = n - 1
	l1 = 0
	d = 0
	while t <= b and l1 <= r1:
		if d == 0:
			for i in range(l1, r1 + 1):
				l.append(matrix[t][i])
			d = 1
			t += 1
		elif d == 1:
			for i in range(t, b + 1):
				l.append(matrix[i][r1])
			d = 2
			r1 -= 1
		elif d == 2:
			for i in range(r1, l1 - 1, -1):
				l.append(matrix[b][i])
			b -= 1
			d = 3
		elif d == 3:
			for i in range(b, t - 1, -1):
				l.append(matrix[i][l1])
			l1 += 1
			d = 4
		d = d % 4
	return l[k - 1]


def findK(arr, m, n, q):
	(k, l) = (0, 0)
	lis = []
	while k < m and l < n:
		for i in range(l, n):
			lis.append(arr[k][i])
		k += 1
		for i in range(k, m):
			lis.append(arr[i][n - 1])
		n -= 1
		if k < m:
			for i in range(n - 1, l - 1, -1):
				lis.append(arr[m - 1][i])
			m -= 1
		if l < n:
			for i in range(m - 1, k - 1, -1):
				lis.append(arr[i][1])
			l += 1
	return lis[q - 1]


def findK(arr, n, m, k):
	newlist = []
	if n == 1:
		for i in range(m):
			newlist.append(arr[0][i])
	if m == 1:
		for i in range(n):
			newlist.append(arr[i][0])
	for i in range(m):
		newlist.append(arr[0][i])
	for j in range(1, n):
		newlist.append(arr[j][m - 1])
	for p in range(m - 2, 0, -1):
		newlist.append(arr[n - 1][p])
	for l in range(n - 1, 0, -1):
		newlist.append(arr[l][0])
	return newlist[k - 1]


def findK(arr, n, m, k):
	r = 0
	c = 0
	while k != 0:
		cc = c
		for j in range(c, m - cc):
			if k == 0:
				return arr[r][c]
			c = j
			k -= 1
		cr = r
		for i in range(r + 1, n - cr):
			if k == 0:
				return arr[r][c]
			r = i
			k -= 1
		cc = c
		for i in range(c - 1, m - cc - 2, -1):
			if k == 0:
				return arr[r][c]
			c = i
			k -= 1
		cr = r
		for j in range(r, n - cr - 2, -1):
			if k == 0:
				return arr[r][c]
			r = j
			k -= 1
	return arr[r][c]


def findK(arr, n, m, k):
	c = 0
	row_b = 0
	row_e = n - 1
	col_b = 0
	col_e = m - 1
	while row_b <= row_e and col_b <= col_e:
		for j in range(col_b, col_e + 1):
			c += 1
			if c == k:
				return arr[row_b][j]
		for i in range(row_b + 1, row_e + 1):
			c += 1
			if c == k:
				return arr[i][col_e]
		for j in range(col_e - 1, col_b - 1, -1):
			c += 1
			if c == k:
				return arr[row_e][j]
		for i in range(row_e - 1, row_b - 1, -1):
			c += 1
			if c == k:
				return arr[i][col_b]
		row_b += 1
		row_e -= 1
		col_b += 1
		col_e -= 1
	return -1


def findK(mat, n, m, k):
	newarr = []
	c = 0
	(firstrow, lastrow) = (0, n - 1)
	(firstcol, lastcol) = (0, m - 1)
	while firstcol <= lastcol and firstrow <= lastrow:
		for i in range(firstcol, lastcol + 1, 1):
			newarr.append(mat[firstrow][i])
		firstrow += 1
		for i in range(firstrow, lastrow + 1, 1):
			newarr.append(mat[i][lastcol])
		lastcol -= 1
		if firstrow <= lastrow:
			for i in range(lastcol, firstcol - 1, -1):
				newarr.append(mat[lastrow][i])
			lastrow -= 1
		if firstcol <= lastcol:
			for i in range(lastrow, firstrow - 1, -1):
				newarr.append(mat[i][firstcol])
			firstcol += 1
	return newarr[k - 1]


def findK(arr, n, m, k):
	total = n * m
	if k > total:
		return 0
	min_row = 0
	min_col = 0
	max_row = n
	max_col = m
	count = 0
	res = []
	while count < total:
		if count < total:
			for i in range(min_col, max_col):
				res.append(arr[min_row][i])
				count += 1
				if len(res) == k:
					return res[-1]
		min_row += 1
		if count < total:
			for i in range(min_row, max_row):
				res.append(arr[i][max_col - 1])
				count += 1
				if len(res) == k:
					return res[-1]
		max_col -= 1
		if count < total:
			for i in range(max_col - 1, min_col - 1, -1):
				res.append(arr[max_row - 1][i])
				count += 1
				if len(res) == k:
					return res[-1]
		max_row -= 1
		if count < total:
			for i in range(max_row - 1, min_row - 1, -1):
				res.append(arr[i][min_col])
				count += 1
				if len(res) == k:
					return res[-1]
		min_col += 1


def findK(arr, n, m, x):
	cnt = 0
	(k, l) = (0, 0)
	while k < n and l < m:
		for i in range(l, m):
			cnt += 1
			if cnt == x:
				return arr[k][i]
		k += 1
		for i in range(k, n):
			cnt += 1
			if cnt == x:
				return arr[i][m - 1]
		m -= 1
		if k < n:
			for i in range(m - 1, l - 1, -1):
				cnt += 1
				if cnt == x:
					return arr[n - 1][i]
			n -= 1
		if l < m:
			for i in range(n - 1, k - 1, -1):
				cnt += 1
				if cnt == x:
					return arr[i][l]
			l += 1
	return 127777


def findK(arr, n, m, k):
	(top, down) = (0, n - 1)
	(left, right) = (0, m - 1)
	while top <= down and left <= right:
		for j in range(left, right + 1):
			k -= 1
			if k == 0:
				return arr[top][j]
		top += 1
		for i in range(top, down + 1):
			k -= 1
			if k == 0:
				return arr[i][right]
		right -= 1
		for j in range(right, left - 1, -1):
			k -= 1
			if k == 0:
				return arr[down][j]
		down -= 1
		for i in range(down, top - 1, -1):
			k -= 1
			if k == 0:
				return arr[i][left]
		left += 1


def findK(a, n, m, k):
	if k > n * m:
		return -1
	u = 0
	d = n - 1
	l = 0
	r = m - 1
	count = 0
	while u <= d and l <= r:
		for i in range(l, r + 1):
			count += 1
			if count == k:
				return a[u][i]
		u += 1
		if u <= d and l <= r:
			for i in range(u, d + 1):
				count += 1
				if count == k:
					return a[i][r]
			r -= 1
		if u <= d and l <= r:
			for i in range(r, l - 1, -1):
				count += 1
				if count == k:
					return a[d][i]
			d -= 1
		if u <= d and l <= r:
			for i in range(d, u - 1, -1):
				count += 1
				if count == k:
					return a[i][l]
			l += 1
	return -1


def findK(arr, n, m, k):
	lst = []
	top = 0
	bottom = n - 1
	left = 0
	right = m - 1
	direction = 0
	while left <= right and top <= bottom:
		if direction == 0:
			for i in range(left, right + 1):
				val = arr[top][i]
				lst.append(val)
			top += 1
		if direction == 1:
			for i in range(top, bottom + 1):
				val = arr[i][right]
				lst.append(val)
			right -= 1
		if direction == 2:
			for i in range(right, left - 1, -1):
				val = arr[bottom][i]
				lst.append(val)
			bottom -= 1
		if direction == 3:
			for i in range(bottom, top - 1, -1):
				val = arr[i][left]
				lst.append(val)
			left += 1
		direction = (direction + 1) % 4
	return lst[k - 1]


from math import ceil

def findK(mat, n, m, k):
	num_layers = ceil(min(n, m) / 2)
	count = 0
	for i in range(num_layers):
		(x, y) = (i, i)
		while x < m - i:
			count += 1
			if count == k:
				return mat[y][x]
			x += 1
		x -= 1
		y += 1
		while y < n - i:
			count += 1
			if count == k:
				return mat[y][x]
			y += 1
		y -= 1
		x -= 1
		while x >= i:
			count += 1
			if count == k:
				return mat[y][x]
			x -= 1
		x += 1
		y -= 1
		while y > i:
			count += 1
			if count == k:
				return mat[y][x]
			y -= 1
	return -1


def findK(arr, n, m, k):
	spirals = min((n + 1) // 2, (m + 1) // 2)
	count = 0
	for s in range(spirals):
		for j in range(s, m - s):
			count += 1
			if count == k:
				return arr[s][j]
		for i in range(1 + s, n - s):
			count += 1
			if count == k:
				return arr[i][m - 1 - s]
		if n - 1 - s > (n - 1) // 2:
			for j in range(m - 2 - s, s - 1, -1):
				count += 1
				if count == k:
					return arr[n - 1 - s][j]
		if s < m // 2:
			for i in range(n - 2 - s, s, -1):
				count += 1
				if count == k:
					return arr[i][s]


def findK(arr, n, m, k):
	ans = [-1]

	def path(i, j, count, dir, k, vis):
		if count == k:
			ans[0] = arr[i][j]
			return True
		vis.add((i, j))
		if dir == 'UP':
			x = i - 1
			y = j
			if x < len(arr) and x >= 0 and (y < len(arr[0])) and (y >= 0):
				if (x, y) not in vis:
					path(x, y, count + 1, 'UP', k, vis)
			else:
				path(i, j, count, 'RIGHT', k, vis)
		if dir == 'RIGHT':
			x = i
			y = j + 1
			if x < len(arr) and x >= 0 and (y < len(arr[0])) and (y >= 0):
				if (x, y) not in vis:
					path(x, y, count + 1, 'RIGHT', k, vis)
			else:
				path(i, j, count, 'DOWN', k, vis)
		if dir == 'DOWN':
			x = i + 1
			y = j
			if x < len(arr) and x >= 0 and (y < len(arr[0])) and (y >= 0):
				if (x, y) not in vis:
					path(x, y, count + 1, 'DOWN', k, vis)
			else:
				path(i, j, count, 'LEFT', k, vis)
		if dir == 'LEFT':
			x = i
			y = j - 1
			if x < len(arr) and x >= 0 and (y < len(arr[0])) and (y >= 0):
				if (x, y) not in vis:
					path(x, y, count + 1, 'LEFT', k, vis)
			else:
				path(i, j, count, 'UP', k, vis)
	path(0, 0, 1, 'RIGHT', k, set())
	return ans[0]


import numpy as np

class Solution:

	def BoundaryTraversal(self, mat, n, m):
		l = []
		travMat = np.ones(shape=(n, m), dtype=int)
		i = 0
		for j in range(m):
			if travMat[i][j] == 1:
				l.append(mat[i][j])
				travMat[i][j] = 0
		j = m - 1
		for i in range(n):
			if travMat[i][j] == 1:
				l.append(mat[i][j])
				travMat[i][j] = 0
		i = n - 1
		for j in range(m):
			if travMat[i][j] == 1:
				l.append(mat[i][m - j - 2])
				travMat[i][j] = 0
		j = 0
		for i in range(n):
			if travMat[i][j] == 1:
				l.append(mat[n - i - 1][j])
				travMat[i][j] = 0
		return (l, travMat)

	def spirallyTraverse(self, matrix, r, c):
		resl = []
		matrix = np.array(matrix)
		matrix[matrix == 0] = -1
		while len(matrix[0]) > 0:
			r = len(matrix)
			c = len(matrix[0])
			(l, travMat) = self.BoundaryTraversal(matrix, r, c)
			a = np.multiply(travMat, matrix)
			aa = []
			for k in a:
				zl = np.trim_zeros(k)
				if len(zl) != 0:
					aa.append(list(zl))
			matrix = aa
			for ll in l:
				if ll == -1:
					ll = 0
				resl.append(ll)
			if len(matrix) == 0:
				break
		return resl

def findK(arr, n, m, k):
	finalL = Solution().spirallyTraverse(arr, n, m)
	return finalL[k - 1]


def findK(arr, n, m, k):
	(r_start, r_end) = (0, n - 1)
	(c_start, c_end) = (0, m - 1)
	(i, j) = (0, 0)
	k = k
	while k:
		while j <= c_end:
			if k == 1:
				return arr[i][j]
			j += 1
			k -= 1
		j -= 1
		i += 1
		r_start += 1
		while i <= r_end:
			if k == 1:
				return arr[i][j]
			i += 1
			k -= 1
		i -= 1
		j -= 1
		c_end -= 1
		while j >= c_start:
			if k == 1:
				return arr[i][j]
			j -= 1
			k -= 1
		j += 1
		i -= 1
		r_end -= 1
		while i >= r_start:
			if k == 1:
				return arr[i][j]
			i -= 1
			k -= 1
		i += 1
		c_start += 1
		j += 1
	return arr[i][j]


def findK(matrix, n, m, k):
	(top, bottom) = (0, n - 1)
	(left, right) = (0, m - 1)
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			k -= 1
			if k == 0:
				return matrix[top][i]
		top += 1
		for j in range(top, bottom + 1):
			k -= 1
			if k == 0:
				return matrix[j][right]
		right -= 1
		for i in range(right, left - 1, -1):
			k -= 1
			if k == 0:
				return matrix[bottom][i]
		bottom -= 1
		for j in range(bottom, top - 1, -1):
			k -= 1
			if k == 0:
				return matrix[j][left]
		left += 1


def findK(arr, n, m, k):
	t = 0
	l = 0
	b = n
	r = m
	arr = []
	while t < b and l < r:
		for i in range(l, r):
			arr.append(matrix[t][i])
		t += 1
		for j in range(t, b):
			arr.append(matrix[j][r - 1])
		r -= 1
		if t < b:
			for i in range(r - 1, l - 1, -1):
				arr.append(matrix[b - 1][i])
			b -= 1
		if l < r:
			for i in range(b - 1, t - 1, -1):
				arr.append(matrix[i][l])
			l += 1
	return arr[k - 1]


def findK(arr, m, n, q):
	k = q
	ans = []
	i = 0
	j = 0
	p = 0
	q = 0
	while n >= 0 and m >= 0:
		while j < n:
			ans.append(arr[i][j])
			j += 1
		j -= 1
		i += 1
		while i < m:
			ans.append(arr[i][j])
			i += 1
		i -= 1
		j -= 1
		while j >= p:
			ans.append(arr[i][j])
			j -= 1
		j += 1
		i -= 1
		while i > q:
			ans.append(arr[i][j])
			i -= 1
		m -= 1
		n -= 1
		j += 1
		p += 1
		q += 1
		i += 1
	return ans[k - 1]