Given a positive integer n that represents dimensions of a 4n x 4n matrix with values from 1 to 4*n*4*n filled from left to right and top to bottom. Your task is to form two coils from matrix and print the coils.
Follow the given examples for better understanding.
 
Example 1:
Input:
n = 1
Output:
10 6 2 3 4 8 12 16
7 11 15 14 13 9 5 1 
Explanation:
The matrix is 
1  2  3  4
5  6  7  8
9  10 11 12
13 14 15 16
So, the two coils are as given in the Ouput.
Example 2:
Input:
n = 2
Output:
36 28 20 21 22 30 38 46
54 53 52 51 50 42 34 26
18 10 2 3 4 5 6 7 8
16 24 32 40 48 56 64
29 37 45 44 43 35 27 19
11 12 13 14 15 23 31 39
47 55 63 62 61 60 59 58
57 49 41 33 25 17 9 1  
Explanation:
Your Task:
You don't need to read input or print anything. Your task is to complete the function formCoils() which takes an Integer n as input and returns a vector of two vectors representing coil1 and coil2.
 
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(n^{2})
 
Constraints:
1 <= n <= 20

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Data structures

Starter code: #User function Template for python3



class Solution:

    def formCoils(self, n):

        # code here 

Solutions:
class Solution:

	def formCoils(self, n):
		ans = [[], []]
		curr = [[4 * n - 1, 4 * n - 1], [0, 0]]
		d0 = [(-1, 0), (0, -1), (1, 0), (0, 1)]
		d1 = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		m = [[0 for _ in range(4 * n)] for _ in range(4 * n)]
		start = 1
		for i in range(4 * n):
			for j in range(4 * n):
				m[i][j] = start
				start += 1
		marked = [[0 for _ in range(4 * n)] for _ in range(4 * n)]
		k = 0
		while len(ans[0]) < 8 * n * n:
			marked[curr[0][0]][curr[0][1]] = 1
			ans[0].append(m[curr[0][0]][curr[0][1]])
			marked[curr[1][0]][curr[1][1]] = 1
			ans[1].append(m[curr[1][0]][curr[1][1]])
			if not (curr[0][0] + d0[k][0] < 4 * n and curr[0][0] + d0[k][0] >= 0 and (curr[0][1] + d0[k][1] >= 0) and (curr[0][1] + d0[k][0] < 4 * n) and (marked[curr[0][0] + d0[k][0]][curr[0][1] + d0[k][1]] == 0)):
				k = (k + 1) % 4
			curr[0][0] += d0[k][0]
			curr[0][1] += d0[k][1]
			curr[1][0] += d1[k][0]
			curr[1][1] += d1[k][1]
		ans[0].reverse()
		ans[1].reverse()
		return ans


class Solution:

	def formCoils(self, n):

		def solve1(mat, r, c):
			arr1 = []
			t = 0
			b = r - 1
			l = 0
			r = c - 1
			dir = 1
			while t <= b and l <= r:
				if dir == 1:
					for i in range(t, b + 1):
						arr1.append(mat[i][l])
					l += 1
					dir = 0
				if dir == 0:
					for i in range(l, r):
						arr1.append(mat[b][i])
					l += 1
					b -= 1
					r -= 1
					dir = 3
				if dir == 3:
					for i in range(b, t, -1):
						arr1.append(mat[i][r])
					dir = 2
					r -= 1
				if dir == 2:
					for i in range(r, l - 1, -1):
						arr1.append(mat[t + 1][i])
					dir = 1
					t += 2
					b -= 1
			return arr1

		def solve2(mat, r, c):
			arr1 = []
			t = 0
			b = r - 1
			l = 0
			r = c - 1
			dir = 3
			while t <= b and l <= r:
				if dir == 3:
					for i in range(b, t - 1, -1):
						arr1.append(mat[i][r])
					dir = 0
					r -= 1
				if dir == 0:
					for i in range(r, l, -1):
						arr1.append(mat[t][i])
					l += 1
					t += 1
					dir = 1
				if dir == 1:
					for i in range(t, b):
						arr1.append(mat[i][l])
					b -= 1
					l += 1
					dir = 2
				if dir == 2:
					for i in range(l, r):
						arr1.append(mat[b][i])
					dir = 3
					t += 1
					r -= 1
					b -= 1
			return arr1
		r = 4 * n
		c = 4 * n
		k = 1
		mat = []
		for i in range(1, r + 1):
			arr = []
			for j in range(1, c + 1):
				arr.append(k)
				k += 1
			mat.append(arr)
		return (solve2(mat, r, c)[::-1], solve1(mat, r, c)[::-1])


class Solution:

	def formCoils(self, n):
		mat = lambda i, j: 4 * n * i + j + 1
		answer = [[], []]

		def getAns(i, j, direction, ans):
			ans.append(mat(i, j))
			step = 2
			while 0 <= i < 4 * n and 0 <= j < 4 * n:
				temp = 1
				while temp <= step:
					if direction == 0:
						i = i - 1
					elif direction == 1:
						j = j + 1
					elif direction == 2:
						i = i + 1
					else:
						j = j - 1
					ans.append(mat(i, j))
					temp += 1
				direction = (direction + 1) % 4
				if direction == 0 or direction == 2:
					step += 2
		direction = 0
		i = 2 * n
		j = 2 * n - 1
		getAns(i, j, direction, answer[0])
		answer[0].pop()
		direction = 2
		i = 2 * n - 1
		j = 2 * n
		getAns(i, j, direction, answer[1])
		answer[1].pop()
		return answer


class Solution:

	def formCoils(self, n):
		mat = lambda i, j: 4 * n * i + j + 1
		answer = [[], []]

		def getAns(i, j, direction, ans):
			ans.append(mat(i, j))
			step = 2
			while 0 <= i < 4 * n and 0 <= j < 4 * n:
				temp = 1
				while temp <= step:
					if direction == 0:
						i = i - 1
					elif direction == 1:
						j = j + 1
					elif direction == 2:
						i = i + 1
					else:
						j = j - 1
					ans.append(mat(i, j))
					temp += 1
				direction = (direction + 1) % 4
				if direction == 0 or direction == 2:
					step += 2
		direction = 0
		i = 2 * n
		j = 2 * n - 1
		getAns(i, j, direction, answer[0])
		answer[0].pop()
		direction = 2
		i = 2 * n - 1
		j = 2 * n
		getAns(i, j, direction, answer[1])
		answer[1].pop()
		return answer
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		ptr = ob.formCoils(n)
		for i in range(2):
			print(*ptr[i])


class Solution:

	def formCoils(self, n):
		mat = [[i + (j - 1) * 4 * n for i in range(1, 4 * n + 1)] for j in range(1, 4 * n + 1)]
		m = mat[-1]
		(x1, y1) = (2 * n, 2 * n - 1)
		(x2, y2) = (2 * n - 1, 2 * n)
		lst1 = [mat[x1][y1]]
		lst2 = [mat[x2][y2]]
		sgn = 1
		for i in range(2, 4 * n - 1, 2):
			for j in range(i):
				x1 += -sgn * 1
				x2 += sgn * 1
				lst1.append(mat[x1][y1])
				lst2.append(mat[x2][y2])
			for j in range(i):
				y1 += sgn * 1
				y2 += -sgn * 1
				lst1.append(mat[x1][y1])
				lst2.append(mat[x2][y2])
			sgn *= -1
		i = 4 * n - 1
		for j in range(i):
			x1 += -sgn * 1
			x2 += sgn * 1
			lst1.append(mat[x1][y1])
			lst2.append(mat[x2][y2])
		return (lst1, lst2)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		ob = Solution()
		ptr = ob.formCoils(n)
		for i in range(2):
			print(*ptr[i])


class Solution:

	def formCoils(self, n):
		Arr = [[0 for _ in range(4 * n)] for _ in range(4 * n)]
		cnt = 1
		for i in range(0, 4 * n):
			for j in range(0, 4 * n):
				Arr[i][j] = cnt
				cnt += 1
		lst1 = []
		direction = 0
		left = 0
		right = 4 * n - 1
		top = 0
		bottom = 4 * n - 1
		while left <= right and top <= bottom:
			if direction == 0:
				for i in range(top, bottom + 1):
					lst1.append(Arr[i][left])
				left += 1
				right -= 1
			if direction == 1:
				for i in range(left, right + 1):
					lst1.append(Arr[bottom][i])
				top += 1
				bottom -= 1
			if direction == 2:
				for i in range(bottom, top - 1, -1):
					lst1.append(Arr[i][right])
				left += 1
				right -= 1
			if direction == 3:
				for i in range(right, left - 1, -1):
					lst1.append(Arr[top][i])
				top += 1
				bottom -= 1
			direction = (direction + 1) % 4
		direction = 0
		left = 0
		right = 4 * n - 1
		top = 0
		bottom = 4 * n - 1
		lst2 = []
		while left <= right and top <= bottom:
			if direction == 0:
				for i in range(bottom, top - 1, -1):
					lst2.append(Arr[i][right])
				right -= 1
				left += 1
			if direction == 1:
				for i in range(right, left - 1, -1):
					lst2.append(Arr[top][i])
				top += 1
				bottom -= 1
			if direction == 2:
				for i in range(top, bottom + 1):
					lst2.append(Arr[i][left])
				left += 1
				right -= 1
			if direction == 3:
				for i in range(left, right + 1):
					lst2.append(Arr[bottom][i])
				bottom -= 1
				top += 1
			direction = (direction + 1) % 4
		Lst = []
		Lst.append(lst2[::-1])
		Lst.append(lst1[::-1])
		return Lst


class Solution:

	def formCoils(self, n):

		def inMatrix(i, j, n):
			return 0 <= i < 4 * n and 0 <= j < 4 * n

		def valFromCoord(i, j, n):
			base = 1 + 4 * n * i
			return base + j
		dirs = ((1, 0), (0, 1), (-1, 0), (0, -1))
		coil1 = [1]
		coil2 = [4 * n * 4 * n]
		i1 = 0
		j1 = 0
		i2 = 4 * n - 1
		j2 = 4 * n - 1
		added = set()
		added.add(1)
		added.add(4 * n * 4 * n)
		dir1 = 0
		dir2 = 2
		while len(added) < 4 * n * 4 * n:
			d1 = dirs[dir1]
			d2 = dirs[dir2]
			while inMatrix(i1 + d1[0], j1 + d1[1], n) and inMatrix(i2 + d2[0], j2 + d2[1], n):
				val1 = valFromCoord(i1 + d1[0], j1 + d1[1], n)
				val2 = valFromCoord(i2 + d2[0], j2 + d2[1], n)
				if val1 not in added and val2 not in added:
					i1 += d1[0]
					j1 += d1[1]
					i2 += d2[0]
					j2 += d2[1]
					added.add(val1)
					coil1.append(val1)
					added.add(val2)
					coil2.append(val2)
				else:
					break
			dir1 = (dir1 + 1) % 4
			dir2 = (dir2 + 1) % 4
		return [coil2[::-1], coil1[::-1]]


class Solution:

	def formCoils(self, n):
		num_cells = (4 * n) ** 2
		num_per_coil = num_cells >> 1
		coil1 = [0] * num_per_coil
		curr = coil1[0] = num_per_coil + 2 * n
		index = 1
		flag = 1
		step = 2
		while index < num_per_coil:
			for i in range(step):
				curr = coil1[index] = curr - 4 * n * flag
				index += 1
				if index >= num_per_coil:
					break
			if index >= num_per_coil:
				break
			for i in range(step):
				curr = coil1[index] = curr + flag
				index += 1
				if index >= num_per_coil:
					break
			flag *= -1
			step += 2
		coil2 = [0] * num_per_coil
		for i in range(num_per_coil):
			coil2[i] = num_cells + 1 - coil1[i]
		return (coil1, coil2)


class Solution:

	def formCoils(self, n):
		rows = 4 * n
		cols = 4 * n
		c_n = rows * cols // 2
		coils1 = [0] * c_n
		coils2 = [0] * c_n
		coils1[0] = 8 * n * n + 2 * n
		curr = coils1[0]
		index = 1
		steps = 2
		op = 1
		while index < c_n:
			num_steps = 0
			while index < c_n and num_steps < steps:
				curr = curr - 4 * n * op
				coils1[index] = curr
				index += 1
				num_steps += 1
			num_steps = 0
			while index < c_n and num_steps < steps:
				curr = curr + op
				coils1[index] = curr
				index += 1
				num_steps += 1
			steps += 2
			op *= -1
		for i in range(c_n):
			coils2[i] = 16 * n * n - coils1[i] + 1
		return [coils1, coils2]


class Solution:

	def formCoils(self, n):
		m = 8 * n * n
		coil1 = [0] * m
		coil1[0] = 8 * n * n + 2 * n
		curr = coil1[0]
		nflg = 1
		step = 2
		index = 1
		while index < m:
			for i in range(step):
				curr = curr - 4 * n * nflg
				coil1[index] = curr
				index += 1
				if index >= m:
					break
			if index >= m:
				break
			for i in range(step):
				curr = curr + nflg
				coil1[index] = curr
				index += 1
				if index >= m:
					break
			nflg = -nflg
			step += 2
		coil2 = [0] * m
		i = 0
		for i in range(m):
			coil2[i] = 16 * n * n + 1 - coil1[i]
		return [coil1, coil2]


class Solution:

	def formCoils(self, n):
		c = 1
		m = []
		for i in range(4 * n):
			m.append([])
			for j in range(4 * n):
				m[i].append(c)
				c += 1
		coil2_dx = [0, 1, 0, -1]
		coil2_dy = [1, 0, -1, 0]
		coil1_dx = [-1, 0, 1, 0]
		coil1_dy = [0, 1, 0, -1]
		coil1_strt = m[2 * n][2 * n - 1]
		coil2_strt = m[2 * n - 1][2 * n]
		coil1 = []
		coil2 = []
		i = 2 * n
		j = 2 * n - 1
		c = 2
		d = 0
		flag = 0
		while True:
			cnt = c
			while cnt > 0:
				if i >= 0 and j >= 0 and (i < 4 * n) and (j < 4 * n):
					coil1.append(m[i][j])
					i += coil1_dx[d]
					j += coil1_dy[d]
				else:
					break
				cnt -= 1
			d = (d + 1) % 4
			if (flag + 1) % 2 == 0:
				c += 2
			flag += 1
			if flag > 4 * n:
				break
		for i in range(len(coil1)):
			coil2.append(16 * n * n + 1 - coil1[i])
		return (coil1, coil2)


def Matrix(n, up, mat):
	if up:
		(i, j) = (n * 2, n * 2 - 1)
	else:
		(i, j) = (n * 2 - 1, n * 2)
	mul = 2
	coil1 = [mat[i][j]]
	flag = True
	while len(coil1) < 8 * n ** 2:
		if up:
			temp = mul
			while i > 0 and temp > 0:
				i -= 1
				temp -= 1
				if i < 0:
					flag = False
					break
				coil1.append(mat[i][j])
			if not flag:
				break
			temp = mul
			while j < n * 4 and temp > 0:
				j += 1
				temp -= 1
				if j >= n * 4:
					flag = False
					break
				coil1.append(mat[i][j])
			if not flag:
				break
			up = False
			mul += 2
		else:
			temp = mul
			while i + 1 < n * 4 and temp > 0:
				i += 1
				temp -= 1
				if i >= n * 4:
					flag = False
					break
				coil1.append(mat[i][j])
			if not flag:
				break
			temp = mul
			while j > 0 and temp > 0:
				j -= 1
				temp -= 1
				if j < 0:
					flag = False
					break
				coil1.append(mat[i][j])
			if not flag:
				break
			up = True
			mul += 2
	return coil1[:8 * n ** 2]

class Solution:

	def formCoils(self, n):
		mat = []
		cur_ind = 1
		for x in range(4 * n):
			row = []
			for y in range(4 * n):
				row.append(cur_ind + y)
			mat.append(row)
			cur_ind = y + cur_ind + 1
		res = [Matrix(n, True, mat), Matrix(n, False, mat)]
		return res


class Solution:

	def formCoils(self, n):
		A = [[0] * 4 * n] * 4 * n
		count = 0
		for i in range(4 * n):
			D = [0] * 4 * n
			for j in range(4 * n):
				count += 1
				D[j] = count
			A[i] = D
		lst1 = []
		lst2 = []
		lst = []
		t = 0
		b = len(A) - 1
		l = 0
		r = len(A[0]) - 1
		dir = 0
		while t <= b and l <= r:
			if dir == 0:
				for i in range(t, b + 1):
					lst.append(A[i][l])
				l += 1
				r -= 1
			elif dir == 1:
				for i in range(l, r + 1):
					lst.append(A[b][i])
				b -= 1
				t += 1
			elif dir == 2:
				for i in range(b, t - 1, -1):
					lst.append(A[i][r])
				r -= 1
				l += 1
			elif dir == 3:
				for i in range(r, l - 1, -1):
					lst.append(A[t][i])
				t += 1
				b -= 1
			dir = (dir + 1) % 4
		lst.reverse()
		lst1 = lst
		lst = []
		t = 0
		b = len(A) - 1
		l = 0
		r = len(A[0]) - 1
		dir = 0
		while t <= b and l <= r:
			if dir == 0:
				for i in range(b, t - 1, -1):
					lst.append(A[i][r])
				r -= 1
				l += 1
			elif dir == 1:
				for i in range(r, l - 1, -1):
					lst.append(A[t][i])
				t += 1
				b -= 1
			elif dir == 2:
				for i in range(t, b + 1):
					lst.append(A[i][l])
				l += 1
				r -= 1
			elif dir == 3:
				for i in range(l, r + 1):
					lst.append(A[b][i])
				b -= 1
				t += 1
			dir = (dir + 1) % 4
		lst.reverse()
		lst2 = lst
		return [lst2, lst1]


class Solution:

	def formCoils(self, n):
		iRowStart = n * 2 + 1
		iColStart = n * 2
		listOne = []
		listTwo = []
		listResult = [listOne, listTwo]
		iRow = iRowStart
		iCol = iColStart
		iLength = 4 * 4 * n * n
		bComplete = False
		iSteps = 2
		iStepCounter = 0
		cDirection = 'U'
		while bComplete == False:
			for iStepCounter in range(iSteps):
				if True:
					iNumber = (iRow - 1) * n * 4 + iCol
					listOne.append(iNumber)
					listTwo.append(iLength - iNumber + 1)
					if iNumber == iLength:
						bComplete = True
				if cDirection == 'U':
					iRow -= 1
				elif cDirection == 'R':
					iCol += 1
				elif cDirection == 'D':
					iRow += 1
				elif cDirection == 'L':
					iCol -= 1
				else:
					pass
			if cDirection == 'S':
				cDirection = 'U'
			elif cDirection == 'U':
				cDirection = 'R'
			elif cDirection == 'R':
				cDirection = 'D'
				iSteps += 2
			elif cDirection == 'D':
				cDirection = 'L'
				if iSteps > 2 * n + 1:
					pass
			elif cDirection == 'L':
				cDirection = 'U'
				iSteps += 2
			else:
				bComplete = True
		return listResult


class Solution:

	def valid(self, n, a):
		if 0 <= a < 4 * n:
			return True
		return False

	def formCoils(self, n):
		arr1 = []
		arr2 = []
		start_r = 4 * n // 2
		start_c = 4 * n // 2 - 1
		top = start_r - 2
		left = start_c - 2
		bottom = start_r + 2
		right = start_c + 2
		arr = []
		while 0 <= start_r < 4 * n and 0 <= start_c < 4 * n:
			for i in range(start_r, top, -1):
				arr1.append(4 * i * n + start_c + 1)
				arr2.append(4 * n * (4 * n - i - 1) + (4 * n - start_c - 1) + 1)
			for i in range(start_c, right):
				arr1.append(4 * n * top + i + 1)
				arr2.append(4 * n * (4 * n - top - 1) + (4 * n - i - 1) + 1)
			for i in range(top, bottom):
				arr1.append(4 * n * i + right + 1)
				arr2.append(4 * n * (4 * n - i - 1) + (4 * n - right - 1) + 1)
			i = right
			while self.valid(n, bottom) and i > left:
				arr1.append(4 * n * bottom + i + 1)
				arr2.append(4 * n * (4 * n - bottom - 1) + (4 * n - i - 1) + 1)
				i -= 1
			start_r += 2
			start_c -= 2
			top -= 2
			bottom += 2
			left -= 2
			right += 2
		arr.append(arr1)
		arr.append(arr2)
		return arr


class Solution:

	def formCoils(self, n):
		coil = [[], []]
		n *= 4
		i1 = n // 2
		j1 = i1 - 1
		i2 = n // 2 - 1
		j2 = i2 + 1
		sign = -1
		k = 2
		while 1:
			for _ in range(k):
				coil[0].append(n * i1 + j1 + 1)
				i1 += sign
				coil[1].append(n * i2 + j2 + 1)
				i2 -= sign
			if i1 == n:
				break
			for _ in range(k):
				coil[0].append(n * i1 + j1 + 1)
				j1 -= sign
				coil[1].append(n * i2 + j2 + 1)
				j2 += sign
			sign = -sign
			k += 2
		return coil


class Solution:

	def formCoils(self, n):
		coil = [2 * n * (4 * n + 1)]
		move = 1
		for step in range(2, 4 * n, 2):
			for _ in range(step):
				coil.append(coil[-1] - 4 * n * move)
			for _ in range(step):
				coil.append(coil[-1] + move)
			move *= -1
		for _ in range(4 * n - 1):
			coil.append(coil[-1] + 4 * n)
		return [coil, [16 * n * n + 1 - x for x in coil]]


class Solution:

	def formCoils(self, n):
		m = n * 4
		a = []
		c = 1
		ans = []
		for i in range(4 * n):
			a.append([])
			for j in range(4 * n):
				a[-1].append(c)
				c += 1
		start = [m // 2, m // 2 - 1]
		limit = m * m // 2
		ans.append([])
		ans[-1].append(a[start[0]][start[1]])
		c = 0
		while True:
			c += 2
			for i in range(c):
				start[0] -= 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			for i in range(c):
				start[1] += 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			c += 2
			for i in range(c):
				start[0] += 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			for i in range(c):
				start[1] -= 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
		start = [m // 2 - 1, m // 2]
		limit = m * m // 2
		ans.append([])
		ans[-1].append(a[start[0]][start[1]])
		c = 0
		while True:
			c += 2
			for i in range(c):
				start[0] += 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			for i in range(c):
				start[1] -= 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			c += 2
			for i in range(c):
				start[0] -= 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
			for i in range(c):
				start[1] += 1
				ans[-1].append(a[start[0]][start[1]])
				if len(ans[-1]) == limit:
					break
			if len(ans[-1]) == limit:
				break
		return ans


class Solution:

	def formCoils(self, n):
		b = []
		c = []
		temp1 = (4 * n) ** 2
		temp2 = 1
		a = 4 * n - 2
		flag = -1
		b.append(temp1)
		c.append(temp2)
		for x in range(4 * n - 1):
			temp1 -= 4 * n
			temp2 += 4 * n
			b.append(temp1)
			c.append(temp2)
		for x in range(2 * n - 1):
			for y in range(a):
				temp1 += flag
				temp2 -= flag
				b.append(temp1)
				c.append(temp2)
			flag *= -1
			for y in range(a):
				temp1 += 4 * n * flag
				temp2 -= 4 * n * flag
				b.append(temp1)
				c.append(temp2)
			a -= 2
		b[:] = b[::-1]
		c[:] = c[::-1]
		return (b, c)


class Solution:

	def formCoils(self, n):
		coil = [2 * n * (4 * n + 1)]
		move = 1
		for i in range(2, 4 * n, 2):
			for j in range(i):
				coil.append(coil[-1] - 4 * n * move)
			for k in range(i):
				coil.append(coil[-1] + move)
			move *= -1
		for i in range(4 * n - 1):
			coil.append(coil[-1] + 4 * n)
		return [coil, [16 * n * n + 1 - x for x in coil]]


class Solution:

	def formCoils(self, n):
		m = n * 4
		table = []
		count = 0
		for i in range(m):
			line = []
			for j in range(m):
				count += 1
				line.append(count)
			table.append(line)
		red = []
		moves = {'d': m, 'u': -m, 'r': 1, 'l': -1}
		red_order = ['d', 'r', 'u', 'l']
		steps = m
		val = 1 - m
		while True:
			for move in red_order:
				for bla in range(steps):
					val += moves[move]
					red.append(val)
				if move == 'd' or move == 'u':
					steps -= 2
			if steps + 1 < 0:
				break
		blue_order = ['u', 'l', 'd', 'r']
		blue = []
		steps = m
		val = m * m + m
		while True:
			for move in blue_order:
				for bla in range(steps):
					val += moves[move]
					blue.append(val)
				if move == 'd' or move == 'u':
					steps -= 2
			if steps < 0:
				break
		return (blue[::-1], red[::-1])


class Solution:

	def formCoils(self, n):
		p = 1
		mat = [[0 for j in range(4 * n)] for i in range(4 * n)]
		for l in range(0, 4 * n):
			for g in range(0, 4 * n):
				mat[l][g] = p
				p += 1
		RS = 4 * n // 2 - 1
		RE = 4 * n // 2 + 1
		CS = 4 * n // 2
		CE = 4 * n // 2
		arr1 = []
		totalElements = 4 * n * (4 * n)
		halfElements = totalElements // 2
		i = halfElements
		while i != 0:
			for j in range(RS, RE):
				arr1.append(mat[j][CE])
				i -= 1
			if i == 0:
				break
			CS = CS - 2
			for j in range(CE, CS - 1, -1):
				arr1.append(mat[RE][j])
				i -= 1
			if i == 0:
				break
			RS = RS - 2
			CE = CE + 2
			for j in range(RE - 1, RS, -1):
				arr1.append(mat[j][CS])
				i -= 1
			if i == 0:
				break
			RE = RE + 2
			for j in range(CS, CE):
				arr1.append(mat[RS][j])
				i -= 1
		totalElements1 = 4 * n * (4 * n)
		halfElements1 = totalElements1 // 2
		RS1 = 4 * n // 2 - 2
		RE1 = 4 * n // 2
		CS1 = 4 * n // 2 - 1
		CE1 = 4 * n // 2 - 1
		arr2 = []
		i1 = halfElements1
		while i1 != 0:
			for j in range(RE1, RS1, -1):
				arr2.append(mat[j][CS1])
				i1 -= 1
			if i1 <= 0:
				break
			CE1 = CE1 + 2
			for j in range(CS1, CE1):
				arr2.append(mat[RS1][j])
				i1 -= 1
			if i1 <= 0:
				break
			RE1 = RE1 + 2
			for j in range(RS1, RE1):
				arr2.append(mat[j][CE1])
				i1 -= 1
			if i1 <= 0:
				break
			CS1 = CS1 - 2
			RS1 = RS1 - 2
			for j in range(CE1, CS1, -1):
				arr2.append(mat[RE1][j])
				i1 -= 1
		arr = [arr2, arr1]
		return arr


class Solution:

	def formCoils(self, n):
		res = [2 * n * (4 * n + 1)]
		move = 1
		for i in range(2, 4 * n, 2):
			for _ in range(i):
				res.append(res[-1] - 4 * n * move)
			for _ in range(i):
				res.append(res[-1] + move)
			move *= -1
		for i in range(4 * n - 1):
			res.append(res[-1] + 4 * n)
		return [res, [16 * n * n + 1 - j for j in res]]


class Solution:

	def formCoils(self, n):
		v = [[], []]
		(ct, i) = (1, n * 2 - 1)
		(k, l) = (i + 1, i)
		e = 4 * n * k + l + 1
		v[0].append(e)
		while ct <= i:
			for j in range(ct * 2):
				if ct % 2 != 0:
					e -= 4 * n
				else:
					e += 4 * n
				v[0].append(e)
			for j in range(ct * 2):
				if ct % 2 == 0:
					e -= 1
				else:
					e += 1
				v[0].append(e)
			ct += 1
		for j in range(4 * n - 1):
			e += 4 * n
			v[0].append(e)
		(ct, e) = (1, 4 * n * l + k + 1)
		v[1].append(e)
		while ct <= i:
			for j in range(ct * 2):
				if ct % 2 != 0:
					e += 4 * n
				else:
					e -= 4 * n
				v[1].append(e)
			for j in range(ct * 2):
				if ct % 2 == 0:
					e += 1
				else:
					e -= 1
				v[1].append(e)
			ct += 1
		for j in range(4 * n - 1):
			e -= 4 * n
			v[1].append(e)
		return v


class Solution:

	def first(self, n, mat):
		arr = []
		j = n - 1
		i = n - 1
		c = -1
		while True:
			while i > c:
				arr.append(mat[i][j])
				i -= 1
			c += 1
			i += 1
			j -= 1
			while j > c:
				arr.append(mat[i][j])
				j -= 1
			i += 1
			j += 1
			while i < n - (c + 1):
				arr.append(mat[i][j])
				i += 1
			i -= 1
			j += 1
			if i == j:
				return arr[::-1]
			c += 1
			while j < n - (c + 1):
				arr.append(mat[i][j])
				j += 1
			j -= 1
			i -= 1

	def second(self, n, mat):
		arr = []
		j = 0
		i = 0
		c = n
		while True:
			while i < c:
				arr.append(mat[i][j])
				i += 1
			c -= 1
			i -= 1
			j += 1
			while j < c:
				arr.append(mat[i][j])
				j += 1
			i -= 1
			j -= 1
			while i > n - (c + 1):
				arr.append(mat[i][j])
				i -= 1
			i += 1
			j -= 1
			if i == j:
				return arr[::-1]
			c -= 1
			while j > n - (c + 1):
				arr.append(mat[i][j])
				j -= 1
			j += 1
			i += 1
		return arr

	def formCoils(self, n):
		mat = []
		for i in range(1, (4 * n) ** 2, 4 * n):
			m = [i for i in range(i, i + 4 * n)]
			mat.append(m)
		arr1 = self.first(4 * n, mat)
		arr2 = self.second(4 * n, mat)
		return [arr1, arr2]


class Solution:

	def formCoils(self, n):
		arr = [2 * n * (4 * n + 1)]
		step = 1
		for i in range(2, 4 * n, 2):
			for _ in range(i):
				arr.append(arr[-1] - 4 * n * step)
			for _ in range(i):
				arr.append(arr[-1] + step)
			step = step * -1
		for _ in range(4 * n - 1):
			arr.append(arr[-1] + 4 * n)
		return [arr, [16 * n * n + 1 - i for i in arr]]


class Solution:

	@staticmethod
	def construct_matrix(n):
		(matrix, st) = ([], 1)
		for i in range(n):
			matrix.append(list(range(st, st + n)))
			st += n
		return matrix

	def formCoils(self, n):
		n *= 4
		matrix = self.construct_matrix(n)
		(coil1, coil2) = ([], [])
		(rmin, rmax, cmin, cmax) = (0, n - 1, 0, n - 1)
		while rmin < rmax and cmin < cmax:
			for i in range(rmin, rmax + 1):
				coil1.append(matrix[i][cmin])
			for j in range(cmin + 1, cmax):
				coil1.append(matrix[rmax][j])
			for i in range(rmax, rmin, -1):
				coil2.append(matrix[i][cmax])
			for j in range(cmax, cmin, -1):
				coil2.append(matrix[rmin][j])
			(coil1, coil2) = (coil2, coil1)
			rmin += 1
			rmax -= 1
			cmin += 1
			cmax -= 1
		return [coil2[::-1], coil1[::-1]]


class Solution:

	def formCoils(self, n):
		coil = [2 * n * (4 * n + 1)]
		coil2 = [2 * n * (4 * n - 1) + 1]
		diff = 1
		for x in range(2, 4 * n, 2):
			for _ in range(x):
				coil.append(coil[-1] - 4 * n * diff)
				coil2.append(coil2[-1] + 4 * n * diff)
			for _ in range(x):
				coil.append(coil[-1] + diff)
				coil2.append(coil2[-1] - diff)
			diff *= -1
		for _ in range(4 * n - 1):
			coil.append(coil[-1] + 4 * n)
			coil2.append(coil2[-1] - 4 * n)
		return [coil, coil2]


class Solution:

	def formCoils(self, n):

		def is_valid(x, y):
			if x >= 0 and x < 4 * n and (y >= 0) and (y < 4 * n):
				return True
			return False

		def rec(x, y, direction, steps):
			update = [[-1, 1], [1, -1]]
			if not is_valid(x, y + steps * update[direction][1]):
				steps = steps - 1
			for i in range(steps):
				y += update[direction][1]
				ans.append(x + y * 4 * n + 1)
			if steps % 2:
				return
			for i in range(steps):
				x += update[direction][0]
				ans.append(x + y * 4 * n + 1)
			direction = 1 - direction
			steps += 2
			rec(x, y, direction, steps)
		ans = []
		half = 4 * n // 2
		(x, y) = (half - 1, half)
		ans.append(x + y * 4 * n + 1)
		rec(x, y, 1, 2)
		ans.append('')
		ret = [ans]
		ans = []
		(x, y) = (half, half - 1)
		ans.append(x + y * 4 * n + 1)
		rec(x, y, 0, 2)
		ans.append('')
		ret.append(ans)
		return ret


class Solution:

	def formCoils(self, n):
		m = 8 * n * n
		ans = [[], []]
		ans[0].append(8 * n * n + 2 * n)
		curr = ans[0][0]
		nfgl = 1
		step = 2
		index = 1
		while index < m:
			for i in range(0, step):
				curr = curr - 4 * n * nfgl
				ans[0].append(curr)
				if len(ans[0]) >= m:
					break
			if len(ans[0]) >= m:
				break
			for i in range(step):
				curr = curr + nfgl
				ans[0].append(curr)
				if len(ans[0]) >= m:
					break
			nfgl = nfgl * -1
			step += 2
		for i in range(m):
			ans[1].append(16 * n * n + 1 - ans[0][i])
		return ans


class Solution:

	def formCoils(self, n):
		c = [2 * n * (4 * n + 1)]
		m = 1
		for s in range(2, 4 * n, 2):
			for i in range(s):
				c.append(c[-1] - 4 * n * m)
			for j in range(s):
				c.append(c[-1] + m)
			m *= -1
		for k in range(4 * n - 1):
			c.append(c[-1] + 4 * n)
		return [c, [16 * n * n + 1 - x for x in c]]


class Solution:

	def formCoils(self, n):

		def mat(x, y):
			return n * x + y + 1
		arr = [[], []]
		n *= 4
		i1 = int(n / 2)
		j1 = i1 - 1
		sign = -1
		k = 2
		i2 = int(n / 2) - 1
		j2 = i2 + 1
		while 1:
			for _ in range(k):
				arr[0].append(mat(i1, j1))
				i1 += sign
				arr[1].append(mat(i2, j2))
				i2 += sign * -1
			if i1 == n:
				break
			for _ in range(k):
				arr[0].append(mat(i1, j1))
				j1 -= sign
				arr[1].append(mat(i2, j2))
				j2 -= sign * -1
			sign *= -1
			k += 2
		return arr


class Solution:

	def formCoils(self, n):
		c = [2 * n * (4 * n + 1)]
		m = 1
		for i in range(2, 4 * n, 2):
			for _ in range(i):
				c.append(c[-1] - 4 * n * m)
			for _ in range(i):
				c.append(c[-1] + m)
			m *= -1
		for _ in range(4 * n - 1):
			c.append(c[-1] + 4 * n)
		return [c, [16 * n * n + 1 - x for x in c]]


class Solution:

	def formCoils(self, n):

		def mat(x, y):
			return n * x + y + 1
		arr = [[], []]
		n *= 4
		i = int(n / 2)
		j = i - 1
		sign = -1
		k = 2
		while i != n - 1 or j != n - 1:
			for _ in range(k):
				arr[0].append(mat(i, j))
				i += sign
			if i == n:
				break
			for _ in range(k):
				arr[0].append(mat(i, j))
				j -= sign
			sign *= -1
			k += 2
		i = int(n / 2) - 1
		j = i + 1
		sign = 1
		k = 2
		while i != 0 or j != 0:
			for _ in range(k):
				arr[1].append(mat(i, j))
				i += sign
			if i < 0:
				break
			for _ in range(k):
				arr[1].append(mat(i, j))
				j -= sign
			sign *= -1
			k += 2
		return arr


class Solution:

	def formCoils(self, n):
		coils = [2 * n * (4 * n + 1)]
		ind = 1
		for i in range(2, 4 * n, 2):
			for j in range(i):
				coils.append(coils[-1] - 4 * n * ind)
			for j in range(i):
				coils.append(coils[-1] + ind)
			ind *= -1
		for i in range(4 * n - 1):
			coils.append(coils[-1] + 4 * n)
		return [coils, [16 * n * n + 1 - x for x in coils]]