Given a matrix as 2D array. Find the reverse spiral traversal of the matrix. 
Example 1:
Input: R = 3, C = 3
  a = {{9, 8, 7},
       {6, 5, 4},
       {3, 2, 1}}
Output: 5 6 3 2 1 4 7 8 9
Explanation: Spiral form of the matrix
in reverse order starts from the centre 
and goes outward.
Example 2:
Input: R = 4, C = 4 
  a = {{1, 2, 3, 4},
       {5, 6, 7, 8},
       {9, 10, 11, 12}, 
       {13, 14, 15, 16}}
Output: 10 11 7 6 5 9 13 14 15 16 12 8 4 3 2 1
Explanation: 
Your Task:  
You dont need to read input or print anything. Complete the function reverseSpiral() which takes R, C and a as input parameters and returns the matrix in reverse spiral form.
Expected Time Complexity: O(R*C)
Expected Auxiliary Space: O(R*C)
Constraints:
1 <= R,C <=100
1 <= a[R][C] <=100

Difficulty: MEDIUM
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(R*C)
Expected Auxiliary Space: O(R*C)

Starter code:
#User function Template for python3

class Solution:

	def reverseSpiral(self, R, C, a):

		# code here



Solutions:
class Solution:

	def reverseSpiral(self, R, C, a):
		(top, left) = (0, 0)
		(bottom, right) = (R - 1, C - 1)
		ans = []
		while top <= bottom and left <= right:
			for i in range(left, right + 1):
				ans.append(a[top][i])
			top += 1
			for i in range(top, bottom + 1):
				ans.append(a[i][right])
			right -= 1
			if top <= bottom:
				for i in range(right, left - 1, -1):
					ans.append(a[bottom][i])
			bottom -= 1
			if left <= right:
				for i in range(bottom, top - 1, -1):
					ans.append(a[i][left])
			left += 1
		ans.reverse()
		return ans


class Solution:

	def reverseSpiral(self, R, C, a):
		res = []
		(left, right) = (0, len(a[0]))
		(top, bottom) = (0, len(a))
		while left < right and top < bottom:
			for i in range(left, right):
				res.append(a[top][i])
			top += 1
			for i in range(top, bottom):
				res.append(a[i][right - 1])
			right -= 1
			if not (top < bottom and left < right):
				break
			for i in range(right - 1, left - 1, -1):
				res.append(a[bottom - 1][i])
			bottom -= 1
			for i in range(bottom - 1, top - 1, -1):
				res.append(a[i][left])
			left += 1
		mat = []
		for i in range(len(res) - 1, -1, -1):
			mat.append(res[i])
		return mat


class Solution:

	def reverseSpiral(self, R, C, a):
		start_row = 0
		start_col = 0
		end_row = R - 1
		end_col = C - 1
		ans = []
		while len(ans) < R * C and start_row <= end_row and (start_col <= end_col):
			for i in range(start_col, end_col + 1):
				ans.append(a[start_row][i])
			start_row += 1
			for i in range(start_row, end_row + 1):
				ans.append(a[i][end_col])
			end_col -= 1
			if len(ans) < R * C and start_col <= end_col:
				for i in range(end_col, start_col - 1, -1):
					ans.append(a[end_row][i])
				end_row -= 1
			if len(ans) < R * C and start_row <= end_row:
				for i in range(end_row, start_row - 1, -1):
					ans.append(a[i][start_col])
				start_col += 1
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, matrix):
		li = matrix.pop(0)
		while len(matrix):
			si = []
			for i in zip(*matrix):
				si.append(i)
			matrix = si[::-1]
			li += matrix.pop(0)
		return li[::-1]


class Solution:

	def reverseSpiral(self, R, C, matrix):
		n = len(matrix)
		m = len(matrix[0])
		left = 0
		right = m - 1
		top = 0
		bottom = n - 1
		ans = []
		while left <= right and top <= bottom:
			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[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		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(a, 0, 0, R, C)
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		left = 0
		right = C - 1
		top = 0
		down = R - 1
		res = []
		while left <= right and top <= down:
			for i in range(left, right + 1):
				res.append(a[top][i])
			top += 1
			if top > down or left > right:
				break
			for i in range(top, down + 1):
				res.append(a[i][right])
			right -= 1
			if top > down or left > right:
				break
			for i in range(right, left - 1, -1):
				res.append(a[down][i])
			down -= 1
			if top > down or left > right:
				break
			for i in range(down, top - 1, -1):
				res.append(a[i][left])
			left += 1
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, matrix):
		li = []
		ans = []
		(l, r) = (0, len(matrix[0]))
		(t, b) = (0, len(matrix))
		while l < r and t < b:
			for i in range(l, r):
				li.append(matrix[t][i])
			t += 1
			for i in range(t, b):
				li.append(matrix[i][r - 1])
			r -= 1
			if not (l < r and t < b):
				break
			for i in range(r - 1, l - 1, -1):
				li.append(matrix[b - 1][i])
			b -= 1
			for i in range(b - 1, t - 1, -1):
				li.append(matrix[i][l])
			l += 1
		return list(reversed(li))


import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def reverseSpiral(self, R, C, a):
		data = {}

		def is_valid(i, j):
			return i >= 0 and i < R and (j >= 0) and (j < C) and ((i, j) not in data)
		ans = []

		def get_ans(i, j, direction):
			ans.append(a[i][j])
			data[i, j] = True
			d = [[0, 1], [1, 0], [0, -1], [-1, 0]]
			(dx, dy) = d[direction]
			key = (i + dx, j + dy)
			if is_valid(*key):
				get_ans(*key, direction)
			else:
				if direction == 3:
					direction = -1
				direction += 1
				(dx, dy) = d[direction]
				key = (i + dx, j + dy)
				if is_valid(*key):
					get_ans(*key, direction)
		get_ans(0, 0, 0)
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		return a and self.reverseSpiral(_, _, list(zip(*a[1:][:]))[::-1]) + list(a[0][:][::-1])


class Solution:

	def reverseSpiral(self, R, C, a):
		top = 0
		bottom = R - 1
		left = 0
		right = C - 1
		dir = 0
		res = []
		while top <= bottom and left <= right:
			if dir == 0:
				for j in range(left, right + 1):
					res.append(a[top][j])
				top += 1
			if dir == 1:
				for i in range(top, bottom + 1):
					res.append(a[i][right])
				right -= 1
			if dir == 2:
				for j in range(right, left - 1, -1):
					res.append(a[bottom][j])
				bottom -= 1
			if dir == 3:
				for i in range(bottom, top - 1, -1):
					res.append(a[i][left])
				left += 1
			dir = (dir + 1) % 4
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		n = min(R, C) // 2
		output = []
		for j in range(n):
			for i in range(j, C - j):
				output.append(a[j][i])
			for i in range(j + 1, R - j - 1):
				output.append(a[i][-j - 1])
			for i in range(j, C - j):
				output.append(a[-j - 1][-i - 1])
			for i in range(j + 1, R - j - 1):
				output.append(a[-i - 1][j])
		for i in range(n, R - n):
			for j in range(n, C - n):
				output.append(a[i][j])
		return output[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		(tR, tC) = (R, C)
		directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
		ans = []
		ans.extend(a[0])
		i = 0
		current = [0, C - 1]
		while True:
			i = (i + 1) % 4
			tR -= 1
			if tR == 0:
				break
			for j in range(1, tR + 1):
				ans.append(a[current[0] + j * directions[i][0]][current[1] + j * directions[i][1]])
			current = [current[0] + tR * directions[i][0], current[1] + tR * directions[i][1]]
			i = (i + 1) % 4
			tC -= 1
			if tC == 0:
				break
			for j in range(1, 1 + tC):
				ans.append(a[current[0] + j * directions[i][0]][current[1] + j * directions[i][1]])
			current = [current[0] + tC * directions[i][0], current[1] + tC * directions[i][1]]
		return list(reversed(ans))


class Solution:

	def reverseSpiral(self, R, C, matrix):
		out = []
		cols = list(zip(*matrix))
		(up, down, left, right) = (0, len(matrix) - 1, 0, len(matrix[0]) - 1)
		arrow = 1
		while up <= down and left <= right:
			if arrow == 1:
				out += matrix[up][left:right + 1]
				up += 1
				arrow = 2
			elif arrow == 2:
				out += list(cols[right][up:down + 1])
				right -= 1
				arrow = 3
			elif arrow == 3:
				out += matrix[down][left:right + 1][::-1]
				down -= 1
				arrow = 4
			else:
				out += list(cols[left][up:down + 1][::-1])
				left += 1
				arrow = 1
		return out[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		l = []
		down = 0
		left = C
		up = R
		right = 0
		count = 0
		if R == 1:
			l = a[0]
		if C == 1:
			for i in range(0, R):
				l.append(a[i][0])
		if C != 1 and R != 1:
			while count < R * C:
				for i in range(right, left):
					if count >= R * C:
						break
					l.append(a[down][i])
					count += 1
				down += 1
				for i in range(down, up):
					if count >= R * C:
						break
					l.append(a[i][left - 1])
					count += 1
				left -= 1
				for i in range(left - 1, right - 1, -1):
					if count >= R * C:
						break
					l.append(a[up - 1][i])
					count += 1
				up -= 1
				for i in range(up - 1, down - 1, -1):
					if count >= R * C:
						break
					l.append(a[i][right])
					count += 1
					if count >= R * C:
						break
				right += 1
		l.reverse()
		return l


class Solution:

	def reverseSpiral(self, R, C, matrix):
		left = 0
		right = C - 1
		top = 0
		bottom = R - 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 list(reversed(ans))


class Solution:

	def reverseSpiral(self, R, C, arr):
		top = left = 0
		right = C - 1
		bottom = R - 1
		dir = 0
		res = []
		while top <= bottom and left <= right:
			if dir == 0:
				for i in range(left, right + 1):
					res.append(arr[top][i])
				top += 1
				dir = 1
			elif dir == 1:
				for i in range(top, bottom + 1):
					res.append(arr[i][right])
				right -= 1
				dir = 2
			elif dir == 2:
				for i in range(right, left - 1, -1):
					res.append(arr[bottom][i])
				bottom -= 1
				dir = 3
			elif dir == 3:
				for i in range(bottom, top - 1, -1):
					res.append(arr[i][left])
				left += 1
				dir = 0
		return res[::-1]


class Solution:

	def reverseSpiral(self, r, c, matrix):
		arr = []
		left = 0
		right = c
		up = r
		down = 0
		count = 0
		while count < r * c:
			for i in range(left, right):
				arr.append(matrix[down][i])
				count += 1
			left += 1
			right -= 1
			if count == r * c:
				break
			for i in range(left, up):
				arr.append(matrix[i][right])
				count += 1
			if count == r * c:
				break
			for i in range(right - 1, down - 1, -1):
				arr.append(matrix[up - 1][i])
				count += 1
			up -= 1
			if count == r * c:
				break
			for i in range(up - 1, down, -1):
				arr.append(matrix[i][down])
				count += 1
			down += 1
		arr.reverse()
		return arr


class Solution:

	def reverseSpiral(self, R, C, A):
		(left, right, top, bottom) = (0, C, 0, R)
		res = []
		while left < right and top < bottom:
			res.extend([A[top][i] for i in range(left, right)])
			top += 1
			res.extend([A[i][right - 1] for i in range(top, bottom)])
			right -= 1
			if not (left < right and top < bottom):
				break
			res.extend([A[bottom - 1][i] for i in range(right - 1, left - 1, -1)])
			bottom -= 1
			res.extend([A[i][left] for i in range(bottom - 1, top - 1, -1)])
			left += 1
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		(sr, sc) = (0, 0)
		res = []
		while sr < R and sc < C:
			for i in range(sc, C):
				res.append(a[sr][i])
			sr += 1
			for i in range(sr, R):
				res.append(a[i][C - 1])
			C -= 1
			if sr < R:
				for i in range(C - 1, sc - 1, -1):
					res.append(a[R - 1][i])
				R -= 1
			if sc < C:
				for i in range(R - 1, sr - 1, -1):
					res.append(a[i][sc])
				sc += 1
		res = list(reversed(res))
		return res


class Solution:

	def reverseSpiral(self, R, C, a):
		direction = ((0, 1), (1, 0), (0, -1), (-1, 0))
		r = R // 2
		c = (C - 1) // 2
		result = a[0]
		i = 0
		c = [0, C - 1]
		while True:
			i = i + 1 & 3
			R -= 1
			if R == 0:
				break
			for j in range(1, R + 1):
				result.append(a[c[0] + j * direction[i][0]][c[1] + j * direction[i][1]])
			c = [c[0] + R * direction[i][0], c[1] + R * direction[i][1]]
			i = i + 1 & 3
			C -= 1
			if C == 0:
				break
			for j in range(1, C + 1):
				result.append(a[c[0] + j * direction[i][0]][c[1] + j * direction[i][1]])
			c = [c[0] + C * direction[i][0], c[1] + C * direction[i][1]]
		return list(reversed(result))


class Solution:

	def reverseSpiral(self, R, C, a):
		li = []
		(k, l) = (0, 0)
		(m, n) = (R, C)
		while k < m and l < n:
			for i in range(l, n):
				li.append(a[k][i])
			k = k + 1
			for i in range(k, m):
				li.append(a[i][n - 1])
			n = n - 1
			if k < m:
				for i in range(n - 1, l - 1, -1):
					li.append(a[m - 1][i])
				m = m - 1
			if l < n:
				for i in range(m - 1, k - 1, -1):
					li.append(a[i][l])
				l = l + 1
		li = li[::-1]
		return li


class Solution:

	def reccSpiral(self, n1, m1, n2, m2, a, vis, ans):
		if n1 <= n2 and m1 <= m2:
			i = n1
			j = m1
			while j <= m2:
				if vis[i][j] == 0:
					ans.append(a[i][j])
					vis[i][j] = 1
					j = j + 1
				else:
					break
			j = j - 1
			i = i + 1
			while i <= n2:
				if vis[i][j] == 0:
					ans.append(a[i][j])
					vis[i][j] = 1
					i = i + 1
				else:
					break
			i = i - 1
			j = j - 1
			while j >= 0:
				if vis[i][j] == 0:
					ans.append(a[i][j])
					vis[i][j] = 1
					j = j - 1
				else:
					break
			i = i - 1
			j = j + 1
			while i >= 0:
				if vis[i][j] == 0:
					ans.append(a[i][j])
					vis[i][j] = 1
					i = i - 1
				else:
					break
			n1 = n1 + 1
			m1 = m1 + 1
			n2 = n2 - 1
			m2 = m2 - 1
			self.reccSpiral(n1, m1, n2, m2, a, vis, ans)

	def reverseSpiral(self, R, C, a):
		vis = [[0 for j in range(C)] for i in range(R)]
		ans = []
		self.reccSpiral(0, 0, R - 1, C - 1, a, vis, ans)
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		res = []
		t = R * C
		(i, j) = (0, 0)
		(r, c) = (R - 1, C - 1)
		cnt = 0
		while cnt < t:
			if cnt < t:
				for k in range(j, c + 1):
					res.append(a[i][k])
					cnt += 1
				i += 1
			if cnt < t:
				for k in range(i, r + 1):
					res.append(a[k][c])
					cnt += 1
				c -= 1
			if cnt < t:
				for k in range(c, j - 1, -1):
					res.append(a[r][k])
					cnt += 1
				r -= 1
			if cnt < t:
				for k in range(r, i - 1, -1):
					res.append(a[k][j])
					cnt += 1
				j += 1
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		rMin = 0
		rMax = R - 1
		cMin = 0
		cMax = C - 1
		r = 0
		c = 0
		cnt = R * C
		ans = []
		nextMove = 1
		while True:
			ans.insert(0, a[r][c])
			cnt -= 1
			if cnt == 0:
				return ans
			if nextMove == 1:
				if c < cMax:
					c += 1
				else:
					r += 1
					rMin += 1
					nextMove = 2
					continue
			if nextMove == 2:
				if r < rMax:
					r += 1
				else:
					c -= 1
					cMax -= 1
					nextMove = 3
					continue
			if nextMove == 3:
				if c > cMin:
					c -= 1
				else:
					r -= 1
					rMax -= 1
					nextMove = 4
					continue
			if nextMove == 4:
				if r > rMin:
					r -= 1
				else:
					c += 1
					cMin += 1
					nextMove = 1
					continue
		return ans


class Solution:

	def reverseSpiral(self, R, C, a):
		(left, top, right, bottom) = (0, 0, C - 1, R - 1)
		direction = 0
		output = []
		while len(output) < R * C:
			if direction == 0:
				for column in range(left, right + 1):
					output.append(a[top][column])
				top += 1
			if direction == 1:
				for row in range(top, bottom + 1):
					output.append(a[row][right])
				right -= 1
			if direction == 2:
				for column in range(right, left - 1, -1):
					output.append(a[bottom][column])
				bottom -= 1
			if direction == 3:
				for row in range(bottom, top - 1, -1):
					output.append(a[row][left])
				left += 1
			direction = (direction + 1) % 4
		output.reverse()
		return output


class Solution:

	def reverseSpiral(self, m, n, a):
		k = 0
		l = 0
		res = []
		while k < m and l < n:
			for i in range(l, n):
				res.append(a[k][i])
			k += 1
			for i in range(k, m):
				res.append(a[i][n - 1])
			n -= 1
			if k < m:
				for i in range(n - 1, l - 1, -1):
					res.append(a[m - 1][i])
				m -= 1
			if l < n:
				for i in range(m - 1, k - 1, -1):
					res.append(a[i][l])
				l += 1
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		visited = [[0 for i in range(C)] for i in range(R)]
		(i, j) = (0, 0)
		flag = 'R'
		ans = []
		while True:
			if flag == 'R':
				if 0 <= j < C and visited[i][j] == 0:
					visited[i][j] = 1
					ans.append(a[i][j])
					j += 1
				else:
					j -= 1
					i += 1
					flag = 'D'
					if i >= R or visited[i][j]:
						break
			elif flag == 'D':
				if 0 <= i < R and visited[i][j] == 0:
					visited[i][j] = 1
					ans.append(a[i][j])
					i += 1
				else:
					i -= 1
					j -= 1
					flag = 'L'
					if visited[i][j]:
						break
			elif flag == 'L':
				if 0 <= j < C and visited[i][j] == 0:
					visited[i][j] = 1
					ans.append(a[i][j])
					j -= 1
				else:
					j += 1
					i -= 1
					flag = 'U'
					if visited[i][j]:
						break
			elif flag == 'U':
				if 0 <= i < R and visited[i][j] == 0:
					visited[i][j] = 1
					ans.append(a[i][j])
					i -= 1
				else:
					i += 1
					j += 1
					flag = 'R'
					if visited[i][j]:
						break
		return ans[::-1]


class Solution:

	def reverseSpiral(self, r, c, a):
		ans = []
		while a:
			ans += a.pop(0)
			try:
				for i in range(len(a) - 1):
					ans.append(a[i].pop())
			except:
				pass
			try:
				t = a.pop()
				t.reverse()
				ans = ans + t
			except:
				pass
			t = []
			try:
				for i in range(len(a)):
					t.append(a[i].pop(0))
			except:
				pass
			t.reverse()
			ans = ans + t
		ans.reverse()
		return ans


class Solution:

	def reverseSpiral(self, R, C, matrix):
		l1 = []
		try:
			while matrix:
				l1 = l1 + matrix[0]
				matrix.pop(0)
				for i in matrix:
					l1.append(i[-1])
					i.pop()
				x = matrix[-1]
				l1 = l1 + x[::-1]
				matrix.pop()
				for i in range(len(matrix) - 1, -1, -1):
					l1.append(matrix[i][0])
					matrix[i].pop(0)
			return l1[::-1]
		except:
			return l1[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):

		def spiralOrder(matrix):
			(sr, sc, er, ec) = (0, 0, len(matrix) - 1, len(matrix[0]) - 1)
			v = []
			while sr <= er and sc <= ec:
				for i in range(sc, ec + 1):
					v.append(matrix[sr][i])
				sr += 1
				for i in range(sr, er + 1):
					v.append(matrix[i][ec])
				ec -= 1
				if sr <= er:
					for i in range(ec, sc - 1, -1):
						v.append(matrix[er][i])
					er -= 1
				if sc <= ec:
					for i in range(er, sr - 1, -1):
						v.append(matrix[i][sc])
					sc += 1
			return v
		return spiralOrder(a)[::-1]


class Solution:

	def reverseSpiral(self, m, n, a):
		l = 0
		r = n - 1
		t = 0
		b = m - 1
		dir = 0
		res = []
		while t <= b and l <= r:
			if dir == 0:
				for i in range(l, r + 1):
					res.append(a[t][i])
				t += 1
			elif dir == 1:
				for i in range(t, b + 1):
					res.append(a[i][r])
				r -= 1
			elif dir == 2:
				for i in range(r, l - 1, -1):
					res.append(a[b][i])
				b -= 1
			else:
				for i in range(b, t - 1, -1):
					res.append(a[i][l])
				l += 1
			dir = (dir + 1) % 4
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		up = 0
		down = R - 1
		left = 0
		right = C - 1
		res = []
		n = R * C
		while len(res) < n:
			for i in range(left, right + 1):
				res.append(a[up][i])
			up += 1
			for i in range(up, down + 1):
				if len(res) < n:
					res.append(a[i][right])
			right -= 1
			for i in range(right, left - 1, -1):
				if len(res) < n:
					res.append(a[down][i])
			down -= 1
			for i in range(down, up - 1, -1):
				if len(res) < n:
					res.append(a[i][left])
			left += 1
		res.reverse()
		return res


class Solution:

	def reverseSpiral(self, R, C, a):
		ans = []
		while len(a) > 0 and len(a[0]) > 0:
			ans += a.pop(0)
			if len(a) == 0:
				break
			for i in range(len(a)):
				ans.append(a[i].pop())
			if len(a[0]) == 0:
				break
			ans += a.pop()[::-1]
			if len(a) == 0:
				break
			for i in range(len(a) - 1, -1, -1):
				ans.append(a[i].pop(0))
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		t = 0
		b = R - 1
		l = 0
		r = C - 1
		ans = []
		while t <= b and l <= r:
			for i in range(l, r + 1):
				ans.append(a[t][i])
			t += 1
			for i in range(t, b + 1):
				ans.append(a[i][r])
			r -= 1
			if t <= b:
				for i in range(r, l - 1, -1):
					ans.append(a[b][i])
				b -= 1
			if l <= r:
				for i in range(b, t - 1, -1):
					ans.append(a[i][l])
				l += 1
		ans.reverse()
		return ans


class Solution:

	def reverseSpiral(self, R, C, a):
		ans = []
		cnt = R * C
		(sr, er, sc, ec) = (0, R - 1, 0, C - 1)
		while cnt:
			for i in range(sc, ec + 1):
				ans.append(a[sr][i])
				cnt -= 1
			sr += 1
			if cnt == 0:
				break
			for i in range(sr, er + 1):
				ans.append(a[i][ec])
				cnt -= 1
			ec -= 1
			if cnt == 0:
				break
			for i in range(ec, sc - 1, -1):
				ans.append(a[er][i])
				cnt -= 1
			er -= 1
			if cnt == 0:
				break
			for i in range(er, sr - 1, -1):
				ans.append(a[i][sc])
				cnt -= 1
			sc += 1
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		ans = []
		(Srow, Erow, Scol, Ecol) = (0, R - 1, 0, C - 1)
		while Srow <= Erow and Scol <= Ecol:
			for i in range(Srow, Ecol + 1):
				ans.append(a[Srow][i])
			Srow += 1
			for i in range(Srow, Erow + 1):
				ans.append(a[i][Ecol])
			Ecol -= 1
			if Srow <= Erow:
				for i in range(Ecol, Scol - 1, -1):
					ans.append(a[Erow][i])
			Erow -= 1
			if Scol <= Ecol:
				for i in range(Erow, Srow - 1, -1):
					ans.append(a[i][Scol])
			Scol += 1
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		i = 0
		j = 0
		res = []
		while i < R and j < C:
			for e in range(j, C):
				res.insert(0, a[i][e])
			i += 1
			for e in range(i, R):
				res.insert(0, a[e][C - 1])
			C -= 1
			if i < R:
				for e in range(C - 1, j - 1, -1):
					res.insert(0, a[R - 1][e])
				R -= 1
			if j < C:
				for e in range(R - 1, i - 1, -1):
					res.insert(0, a[e][j])
				j += 1
		return res


class Solution:

	def reverseSpiral(self, R, C, a):
		rs = 0
		re = len(a) - 1
		cs = 0
		ce = len(a[0]) - 1
		t = R * C
		count = 0
		l = []
		while rs <= re and cs <= ce:
			for i in range(cs, ce + 1):
				l.append(a[rs][i])
				count = count + 1
			rs = rs + 1
			for i in range(rs, re + 1):
				l.append(a[i][ce])
				count = count + 1
			ce = ce - 1
			if not rs > re:
				for i in range(ce, cs - 1, -1):
					l.append(a[re][i])
					count = count + 1
				re = re - 1
			if not cs > ce:
				for i in range(re, rs - 1, -1):
					l.append(a[i][cs])
					count = count + 1
				cs = cs + 1
		return l[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		t = n = R * C
		(r, c) = (0, 0)
		(rn, cn) = (R, C)
		li = []
		ans = []
		if rn == 1:
			ans = a[0]
			ans.reverse()
			return ans
		if cn == 1:
			for i in range(rn):
				ans.append(a[i][0])
			ans.reverse()
			return ans
		while t != 0:
			for i in range(c, cn):
				li.append(a[r][i])
				t -= 1
			if t == 0:
				break
			r += 1
			for i in range(r, rn):
				li.append(a[i][cn - 1])
				t -= 1
			if t == 0:
				break
			cn -= 1
			for i in range(cn - 1, c - 1, -1):
				li.append(a[rn - 1][i])
				t -= 1
			if t == 0:
				break
			rn -= 1
			for i in range(rn - 1, r - 1, -1):
				li.append(a[i][c])
				t -= 1
			if t == 0:
				break
			c += 1
		ans = li[:n]
		ans.reverse()
		return ans


class Solution:

	def reverseSpiral(self, R, C, a):
		vectors = [(0, 1), (1, 0), (0, -1), (-1, 0)]
		visited = [[False for _ in range(C)] for _ in range(R)]
		current_vector_index = 0
		current_vector = vectors[current_vector_index]
		(x, y) = (0, 0)
		nums_count = R * C
		i = 0
		result = []
		while True:
			result.append(a[x][y])
			if i == nums_count - 1:
				break
			visited[x][y] = True
			while True:
				(next_x, next_y) = (x + current_vector[0], y + current_vector[1])
				if not (self.is_outside(next_x, R) or self.is_outside(next_y, C) or visited[next_x][next_y]):
					break
				current_vector_index = (current_vector_index + 1) % len(vectors)
				current_vector = vectors[current_vector_index]
			(x, y) = (next_x, next_y)
			i += 1
		return result[::-1]

	def is_outside(self, coord, limit):
		return coord < 0 or coord >= limit


class Solution:

	def reverseSpiral(self, R, C, a):
		ans = []
		b = [0] * (R * C + 1)
		k = l = z = 0
		size = R * C
		while k < R and l < C:
			for i in range(l, C):
				val = a[k][i]
				b[z] = val
				z += 1
			k += 1
			for i in range(k, R):
				val = a[i][C - 1]
				b[z] = val
				z += 1
			C -= 1
			if k < R:
				for i in range(C - 1, l - 1, -1):
					val = a[R - 1][i]
					b[z] = val
					z += 1
				R -= 1
			if l < C:
				for i in range(R - 1, k - 1, -1):
					val = a[i][l]
					b[z] = val
					z += 1
				l += 1
		b = b[:-1]
		return b[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		row_st = 0
		col_st = 0
		row_end = R - 1
		col_end = C - 1
		maxi = R * C
		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(a[row_st][i])
					count += 1
			row_st += 1
			if count < maxi:
				for i in range(row_st, row_end + 1):
					ls.append(a[i][col_end])
					count += 1
			col_end -= 1
			if count < maxi:
				for i in range(col_end, col_st - 1, -1):
					ls.append(a[row_end][i])
					count += 1
			row_end -= 1
			if count < maxi:
				for i in range(row_end, row_st - 1, -1):
					ls.append(a[i][col_st])
					count += 1
			col_st += 1
		ls.reverse()
		return ls


class Solution:

	def reverseSpiral(self, q, c, a):
		li = []
		(l, r) = (0, c)
		(t, b) = (0, q)
		while l < r and t < b:
			for i in range(l, r):
				li.append(a[t][i])
			t += 1
			for i in range(t, b):
				li.append(a[i][r - 1])
			r -= 1
			if not (l < r and t < b):
				break
			for i in range(r - 1, l - 1, -1):
				li.append(a[b - 1][i])
			b -= 1
			for i in range(b - 1, t - 1, -1):
				li.append(a[i][l])
			l += 1
		return list(reversed(li))


class Solution:

	def reverseSpiral(self, r, c, res):
		if not res:
			return res
		(st_row, st_col) = (0, 0)
		(end_row, end_col) = (r, c)
		l = []
		while st_row < end_row or st_col < end_col:
			if st_row < end_row:
				for i in range(st_col, end_col):
					l.append(res[st_row][i])
			st_row += 1
			if st_col < end_col:
				for i in range(st_row, end_row):
					l.append(res[i][end_col - 1])
			end_col -= 1
			if st_row < end_row:
				for i in range(end_col - 1, st_col - 1, -1):
					l.append(res[end_row - 1][i])
			end_row -= 1
			if st_col < end_col:
				for i in range(end_row - 1, st_row - 1, -1):
					l.append(res[i][st_col])
			st_col += 1
		return l[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		result = []
		i = 0
		j = 0
		iDelta = 0
		jDelta = 1
		if C == 1:
			iDelta = 1
			jDelta = 0
		while len(result) < R * C:
			result.append(a[i][j])
			i += iDelta
			j += jDelta
			if jDelta == 1 and j + i == C - 1:
				jDelta = 0
				iDelta = 1
			elif iDelta == 1 and i + C - j == R:
				jDelta = -1
				iDelta = 0
			elif jDelta == -1 and j + i == R - 1:
				jDelta = 0
				iDelta = -1
			elif iDelta == -1 and i == j + 1:
				jDelta = 1
				iDelta = 0
		return list(reversed(result))


class Solution:

	def reverseSpiral(self, R, C, a):
		z = []
		row = 0
		col = 0
		while row < R and col < C:
			for i in range(col, C):
				z.append(a[row][i])
			row = row + 1
			for i in range(row, R):
				z.append(a[i][C - 1])
			C = C - 1
			if row < R:
				for i in range(C - 1, col - 1, -1):
					z.append(a[R - 1][i])
				R = R - 1
			if col < C:
				for i in range(R - 1, row - 1, -1):
					z.append(a[i][col])
				col = col + 1
		return z[::-1]


class Solution:

	def reverseSpiral(self, R, C, matrix):
		(top, bottom, left, right) = (0, len(matrix) - 1, 0, len(matrix[0]) - 1)
		direction = 0
		ans = []
		while top <= bottom and left <= right:
			if direction == 0:
				for i in range(left, right + 1):
					ans.append(matrix[top][i])
				top += 1
			elif direction == 1:
				for i in range(top, bottom + 1):
					ans.append(matrix[i][right])
				right -= 1
			elif direction == 2:
				for i in range(right, left - 1, -1):
					ans.append(matrix[bottom][i])
				bottom -= 1
			elif direction == 3:
				for i in range(bottom, top - 1, -1):
					ans.append(matrix[i][left])
				left += 1
			direction = (direction + 1) % 4
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		out = []
		if R == 0:
			return out
		r_b = 0
		c_b = 0
		r_e = R - 1
		c_e = C - 1
		while r_b <= r_e and c_b <= c_e:
			for i in range(c_b, c_e + 1):
				out.append(a[r_b][i])
			r_b += 1
			for i in range(r_b, r_e + 1):
				out.append(a[i][c_e])
			c_e -= 1
			if r_b <= r_e:
				for i in range(c_e, c_b - 1, -1):
					out.append(a[r_e][i])
				r_e -= 1
			if c_b <= c_e:
				for i in range(r_e, r_b - 1, -1):
					out.append(a[i][c_b])
				c_b += 1
		return out[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		count = 0
		ans = []
		mi_c = 0
		mi_r = 0
		ma_r = R - 1
		ma_c = C - 1
		while mi_r <= ma_r and mi_c <= ma_c:
			for i in range(mi_c, ma_c + 1):
				ans.append(a[mi_r][i])
				count += 1
			mi_r += 1
			if count >= R * C:
				break
			for i in range(mi_r, ma_r + 1):
				ans.append(a[i][ma_c])
				count += 1
			ma_c -= 1
			if count >= R * C:
				break
			for i in range(ma_c, mi_c - 1, -1):
				ans.append(a[ma_r][i])
				count += 1
			ma_r -= 1
			if count >= R * C:
				break
			for i in range(ma_r, mi_r - 1, -1):
				ans.append(a[i][mi_c])
				count += 1
			mi_c += 1
		ans.reverse()
		return ans


from math import ceil

class Solution:

	def reverseSpiral(self, R, C, a):
		(r, c) = (R, C)
		res = []
		cur = 0
		for cur in range(ceil(min(R, C) / 2)):
			i = j = cur
			while j < C:
				res.append(a[i][j])
				j += 1
			j -= 1
			i += 1
			while i < R:
				res.append(a[i][j])
				i += 1
			i -= 1
			j -= 1
			while j >= cur:
				res.append(a[i][j])
				j -= 1
			j += 1
			i -= 1
			while i > cur:
				res.append(a[i][j])
				i -= 1
			R -= 1
			C -= 1
		while len(res) > r * c:
			res.pop()
		res.reverse()
		return res


import sys
sys.setrecursionlimit(1000000)

class Solution:

	def reverseSpiral(self, R, C, mat):

		def isvalid(i, j):
			return i >= 0 and j >= 0 and (i < R) and (j < C) and mat[i][j]
		self.result = []
		self.dir = 'R'
		self.len = 0
		self.N = R * C

		def solve(i, j):
			self.result.append(mat[i][j])
			self.len += 1
			if self.len == self.N:
				return
			mat[i][j] = 0
			if self.dir == 'R':
				if isvalid(i, j + 1):
					solve(i, j + 1)
				else:
					self.dir = 'D'
					solve(i + 1, j)
			elif self.dir == 'D':
				if isvalid(i + 1, j):
					solve(i + 1, j)
				else:
					self.dir = 'L'
					solve(i, j - 1)
			elif self.dir == 'L':
				if isvalid(i, j - 1):
					solve(i, j - 1)
				else:
					self.dir = 'U'
					solve(i - 1, j)
			elif isvalid(i - 1, j):
				solve(i - 1, j)
			else:
				self.dir = 'R'
				solve(i, j + 1)
		solve(0, 0)
		return self.result[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		rows = len(a)
		cols = len(a[0])
		(top, down, left, right) = (0, rows - 1, 0, cols - 1)
		move = 0
		res = []
		while top <= down and left <= right:
			if move == 0:
				for i in range(left, right + 1, 1):
					res.append(a[top][i])
				top += 1
				move = 1
			elif move == 1:
				for i in range(top, down + 1, 1):
					res.append(a[i][right])
				right -= 1
				move = 2
			elif move == 2:
				for i in range(right, left - 1, -1):
					res.append(a[down][i])
				down -= 1
				move = 3
			elif move == 3:
				for i in range(down, top - 1, -1):
					res.append(a[i][left])
				left += 1
				move = 0
		return res[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		left = right = up = down = False
		ans = []
		i = 0
		j = 0
		(rmin, rmax, cmin, cmax) = (0, R, 0, C)
		right = True
		while 0 <= i < R and 0 <= j < C and (a[i][j] != -1):
			ans.append(a[i][j])
			a[i][j] = -1
			if right:
				j += 1
				if j == cmax:
					j -= 1
					i += 1
					rmin += 1
					right = False
					down = True
			elif left:
				j -= 1
				if j < cmin:
					j += 1
					rmax -= 1
					i -= 1
					left = False
					up = True
			elif up:
				i -= 1
				if i < rmin:
					i += 1
					j += 1
					cmin += 1
					right = True
					up = False
			elif down:
				i += 1
				if i == rmax:
					i -= 1
					j -= 1
					cmax -= 1
					down = False
					left = True
		return ans[::-1]


class Solution:

	def reverseSpiral(self, R, C, a):
		top = 0
		bottom = R - 1
		left = 0
		right = C - 1
		c = []
		d = 0
		while top <= bottom and left <= right:
			if d == 0:
				for i in range(left, right + 1):
					c.append(a[top][i])
				top += 1
			if d == 1:
				for i in range(top, bottom + 1):
					c.append(a[i][right])
				right -= 1
			if d == 2:
				for i in range(right, left - 1, -1):
					c.append(a[bottom][i])
				bottom -= 1
			if d == 3:
				for i in range(bottom, top - 1, -1):
					c.append(a[i][left])
				left += 1
			d = (d + 1) % 4
		c.reverse()
		return c


class Solution:

	def reverseSpiral(self, R, C, a):
		ans = []
		j = 0
		k = 0
		while j < R and k < C:
			for i in range(k, C):
				ans.append(a[j][i])
			j += 1
			for i in range(j, R):
				ans.append(a[i][C - 1])
			C -= 1
			if j < R:
				for i in range(C - 1, k - 1, -1):
					ans.append(a[R - 1][i])
				R -= 1
			if k < C:
				for i in range(R - 1, j - 1, -1):
					ans.append(a[i][k])
				k += 1
		ans.reverse()
		return ans


class Solution:

	def reverseSpiral(self, R, C, a):
		top = left = 0
		right = C - 1
		down = R - 1
		dirc = 0
		resArr = []
		while top <= down and left <= right:
			if dirc == 0:
				for i in range(left, right + 1):
					resArr.append(a[top][i])
				top += 1
			elif dirc == 1:
				for i in range(top, down + 1):
					resArr.append(a[i][right])
				right -= 1
			elif dirc == 2:
				for i in range(right, left - 1, -1):
					resArr.append(a[down][i])
				down -= 1
			elif dirc == 3:
				for i in range(down, top - 1, -1):
					resArr.append(a[i][left])
				left += 1
			dirc = (dirc + 1) % 4
		return resArr[::-1]


class Solution:

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


class Solution:

	def reverseSpiral(self, r, c, mat):
		ans = []
		while mat:
			ans.extend(mat.pop(0))
			if not mat:
				break
			for i in range(len(mat)):
				ans.append(mat[i].pop(-1))
			mat = list(filter(lambda x: len(x), mat))
			if not mat:
				break
			ans.extend(mat.pop(-1)[::-1])
			mat = list(filter(lambda x: len(x), mat))
			if not mat:
				break
			for i in range(len(mat) - 1, -1, -1):
				ans.append(mat[i].pop(0))
			mat = list(filter(lambda x: len(x), mat))
		return ans[::-1]