Given a matrix M of n*n size, the task is to complete the function which prints its elements in a diagonal pattern as depicted below.
 
 
Example 1:
Input:
N = 3
mat[][] = {{1 2 3},{4 5 6},{7 8 9}}
Output: 1 2 4 7 5 3 6 8 9
Example 2:
Input:
N = 2
mat[][] = {{1 2},{3 4}}
Output: 1 2 3 4
Your Task:
You only need to implement the given function matrixDiagonally() which returns a list containing the matrix diagonally. Do not read input, instead use the arguments given in the function. Print the elements in Matrix in a diagonal pattern.
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)
Constraints:
1<=N<=100

Difficulty: EASY
Tags: Matrices

Data structures
Skill types: Data structures
Expected Time Complexity: O(N*M)
Expected Auxiliary Space: O(1)

Starter code:
# Your task is to complete this function



class Solution:

    def matrixDiagonally(self,mat):

        # code here

Solutions:
class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		m = len(mat[0])
		list = [[] for i in range(n + m - 1)]
		for i in range(n):
			for j in range(m):
				sum = i + j
				if sum % 2 == 0:
					list[sum].insert(0, mat[i][j])
				else:
					list[sum].append(mat[i][j])
		res = []
		for i in list:
			for j in i:
				res.append(j)
		return res


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		total = n * n - 1
		count = 0
		arr = []
		di = {'up': 'down', 'down': 'up'}
		cdi = 'up'
		i = j = 0
		while count <= total:
			if cdi == 'up':
				if i == 0 and j != n - 1:
					arr.append(mat[i][j])
					cdi = di['up']
					j += 1
				elif j == n - 1:
					arr.append(mat[i][j])
					cdi = di['up']
					i += 1
				else:
					arr.append(mat[i][j])
					i -= 1
					j += 1
			elif j == 0 and i != n - 1:
				arr.append(mat[i][j])
				cdi = di['down']
				i += 1
			elif i == n - 1:
				arr.append(mat[i][j])
				cdi = di['down']
				j += 1
			else:
				arr.append(mat[i][j])
				i += 1
				j -= 1
			count += 1
		return arr


class Solution:

	def matrixDiagonally(self, mat):
		rev = True
		i = j = 0
		n = len(mat)
		res = []
		while i >= 0 and i < n and (j >= 0) and (j < n):
			if rev:
				(pi, pj) = (i, j)
				while i >= 0 and i < n and (j >= 0) and (j < n):
					res.append(mat[i][j])
					(pi, pj) = (i, j)
					i -= 1
					j += 1
				(i, j) = (pi, pj)
				if j == n - 1:
					i += 1
				else:
					j += 1
			else:
				(pi, pj) = (i, j)
				while i >= 0 and i < n and (j >= 0) and (j < n):
					res.append(mat[i][j])
					(pi, pj) = (i, j)
					i += 1
					j -= 1
				(i, j) = (pi, pj)
				if i == n - 1:
					j += 1
				else:
					i += 1
			rev = not rev
		return res


class Solution:

	def matrixDiagonally(self, mat):
		dic = {i: [] for i in range(len(mat) * len(mat) + 1)}
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				dic[i + j].append(mat[i][j])
		ans = []
		for i in range(len(mat) * len(mat) + 1):
			if i % 2 == 0:
				ans += dic[i][::-1]
			else:
				ans += dic[i]
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		m = len(mat)
		n = len(mat[0])
		ll = []
		cnt = 1
		for i in range(n):
			x = 0
			y = i
			l = []
			while (x >= 0 and y >= 0) and (x < m and y < n):
				l.append(mat[x][y])
				x += 1
				y -= 1
			if cnt % 2 == 0:
				ll += l
			else:
				ll += l[::-1]
			cnt += 1
		for i in range(1, m):
			x = i
			y = n - 1
			l = []
			while (x >= 0 and y >= 0) and (x < m and y < n):
				l.append(mat[x][y])
				x += 1
				y -= 1
			if cnt % 2 == 0:
				ll += l
			else:
				ll += l[::-1]
			cnt += 1
		return ll


class Solution:

	def matrixDiagonally(self, mat):
		N = len(mat)
		ls = []
		d_up = True
		r = 0
		c = 0
		while r < N and c < N:
			if d_up:
				while r > 0 and c < N - 1:
					ls.append(mat[r][c])
					r -= 1
					c += 1
				ls.append(mat[r][c])
				if c == N - 1:
					r += 1
				else:
					c += 1
			else:
				while c > 0 and r < N - 1:
					ls.append(mat[r][c])
					c -= 1
					r += 1
				ls.append(mat[r][c])
				if r == N - 1:
					c += 1
				else:
					r += 1
			d_up = not d_up
		return ls


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		m = []
		i = 0
		j = 0
		k = 0
		isUp = True
		while k < n * n:
			if isUp:
				while i >= 0 and j < n:
					m.append(mat[i][j])
					k += 1
					j += 1
					i -= 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i = i + 2
					j -= 1
			else:
				while j >= 0 and i < n:
					m.append(mat[i][j])
					k += 1
					i += 1
					j -= 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j = j + 2
					i -= 1
			isUp = not isUp
		return m


class Solution:

	def matrixDiagonally(self, mat):
		t = []
		N = len(mat)
		A = mat
		for i in range(N):
			row = 0
			col = i
			while row < N and col >= 0:
				if (row + col) % 2 != 0:
					t.append(A[row][col])
				else:
					t.append(A[col][row])
				row += 1
				col -= 1
		for j in range(1, N):
			row = j
			col = N - 1
			while row < N and col >= 0:
				if (row + col) % 2 != 0:
					t.append(A[row][col])
				else:
					t.append(A[col][row])
				row += 1
				col -= 1
		return t


class Solution:

	def matrixDiagonally(self, mat):
		output = []
		n = len(mat)
		for i in range(n):
			items = []
			for j in range(i + 1):
				items.append(mat[j][i - j])
			if i % 2:
				output += items
			else:
				output += items[::-1]
		for i in range(1, n):
			items = []
			for j in range(i, n):
				items.append(mat[j][n - j + i - 1])
			if (n + i) % 2:
				output += items[::-1]
			else:
				output += items
		return output


from collections import defaultdict

class Solution:

	def matrixDiagonally(self, mat):
		d = defaultdict(list)
		visited = set()
		q = [((0, 0), 0)]
		n = len(mat)
		while q:
			(node, lvl) = q.pop(0)
			(i, j) = node
			d[lvl].append(mat[i][j])
			if i + 1 < n and (i + 1, j) not in visited:
				visited.add((i + 1, j))
				q.append(((i + 1, j), lvl + 1))
			if j + 1 < n and (i, j + 1) not in visited:
				visited.add((i, j + 1))
				q.append(((i, j + 1), lvl + 1))
		x = []
		for i in range(len(d)):
			p = d[i]
			if i % 2 == 1:
				p = p[::-1]
			for j in p:
				x.append(j)
		return x


class Solution:

	def matrixDiagonally(self, mat):
		if len(mat) == 0:
			return []
		m = len(mat)
		n = len(mat[0])
		row = 0
		col = 0
		res = []
		isUp = True
		while row < m and col < n:
			if isUp:
				while row > 0 and col < n - 1:
					res.append(mat[row][col])
					row -= 1
					col += 1
				res.append(mat[row][col])
				if col == n - 1:
					row += 1
				else:
					col += 1
			else:
				while row < m - 1 and col > 0:
					res.append(mat[row][col])
					row += 1
					col -= 1
				res.append(mat[row][col])
				if row == m - 1:
					col += 1
				else:
					row += 1
			isUp = not isUp
		return res


class Solution:

	def matrixDiagonally(self, mat):
		r = c = len(mat)
		res = [[] for i in range(c + r - 1)]
		for i in range(r):
			for j in range(c):
				s = i + j
				if s % 2 == 0:
					res[s].insert(0, mat[i][j])
				else:
					res[s].append(mat[i][j])
		return sum(res, [])


class Solution:

	def matrixDiagonally(self, mat):
		m = len(mat)
		n = len(mat[0])
		k = 0
		retarray = []
		boolval = True
		for i in range(n):
			l = i
			if not boolval:
				while k <= i:
					retarray.append(mat[k][l])
					k += 1
					l -= 1
				k = 0
				boolval = not boolval
			else:
				while k <= i:
					retarray.append(mat[l][k])
					k += 1
					l -= 1
				k = 0
				boolval = not boolval
		k = n - 1
		for i in range(1, n):
			l = i
			if boolval:
				while l < n:
					retarray.append(mat[k][l])
					k -= 1
					l += 1
				k = n - 1
				boolval = not boolval
			else:
				while l < n:
					retarray.append(mat[l][k])
					k -= 1
					l += 1
				k = n - 1
				boolval = not boolval
		return retarray


class Solution:

	def matrixDiagonally(self, mat):
		rows = colm = len(mat)
		ans = [[] for i in range(rows + colm - 1)]
		for i in range(rows):
			for j in range(colm):
				ij = i + j
				if ij & 1 != 1:
					ans[ij].insert(0, mat[i][j])
				else:
					ans[ij].append(mat[i][j])
		return sum(ans, [])


class Solution:

	def matrixDiagonally(self, li):
		n = len(li)
		ans = [[] for i in range(n + n - 1)]
		j = 0
		for i in range(n):
			x = i
			y = j
			while x >= 0 and y < n:
				ans[i + j].append(li[x][y])
				x -= 1
				y += 1
		j = n - 1
		for i in range(1, n):
			x = i
			y = j
			while x < n and y >= 0:
				ans[i + j].append(li[y][x])
				x += 1
				y -= 1
		output = []
		for i in range(len(ans)):
			if i % 2 != 0:
				for j in range(len(ans[i]) - 1, -1, -1):
					output.append(ans[i][j])
			else:
				for j in range(len(ans[i])):
					output.append(ans[i][j])
		return output


class Solution:

	def matrixDiagonally(self, mat):
		(r, c) = (0, 0)
		isUp = True
		count = 0
		n = len(mat)
		ans = []
		while count < n * n:
			if isUp:
				while r >= 0 and c < n:
					ans.append(mat[r][c])
					r -= 1
					c += 1
					count += 1
				if r < 0 and c < n:
					r = 0
				if c == n:
					r += 2
					c -= 1
			else:
				while c >= 0 and r < n:
					ans.append(mat[r][c])
					r += 1
					c -= 1
					count += 1
				if c < 0 and r < n:
					c = 0
				if r == n:
					c += 2
					r -= 1
			isUp = not isUp
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		n = len(matrix)
		mode = 0
		it = 0
		lower = 0
		temp = []
		for t in range(2 * n - 1):
			t_ = t
			if t_ >= n:
				mode += 1
				t_ = n - 1
				it -= 1
				lower += 1
			else:
				lower = 0
				it += 1
			for i in range(t_, lower - 1, -1):
				this = t_ + lower - i
				if (t_ + mode) % 2 == 0:
					temp.append(matrix[i][this])
				else:
					temp.append(matrix[this][i])
		return temp


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		k = 0
		i = 0
		j = 0
		flag = True
		result = []
		while k < n * n:
			if flag:
				while i >= 0 and j < n:
					result.append(mat[i][j])
					i -= 1
					j += 1
					k += 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i += 2
					j -= 1
			else:
				while j >= 0 and i < n:
					result.append(mat[i][j])
					j -= 1
					i += 1
					k += 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j += 2
					i -= 1
			flag = not flag
		return result


class Solution:

	def matrixDiagonally(self, mat):
		(row, column) = (len(mat), len(mat[0]))
		arr = []
		for i in range(row):
			diag = []
			a = i
			j = 0
			while a >= 0 and j < column:
				diag.append(mat[a][j])
				a -= 1
				j += 1
			arr.append(diag)
		for j in range(1, column):
			diag = []
			a = j
			i = row - 1
			while a < column and i >= 0:
				diag.append(mat[i][a])
				i -= 1
				a += 1
			arr.append(diag)
		for i in range(1, len(arr), 2):
			arr[i] = arr[i][::-1]
		return [x for y in arr for x in y]


class Solution:

	def matrixDiagonally(self, mat):
		l = []
		n = len(mat)
		c = 1
		for i in range(n):
			k = i
			j = 0
			g = []
			while k >= 0:
				g.append(mat[j][k])
				k -= 1
				j += 1
			if c == 0:
				l.extend(g)
			else:
				l.extend(g[::-1])
			c = c ^ 1
		for i in range(1, n):
			k = i
			j = n - 1
			g = []
			while k < n:
				g.append(mat[k][j])
				k += 1
				j -= 1
			if c == 0:
				l.extend(g)
			else:
				l.extend(g[::-1])
			c = c ^ 1
		return l


def level_range(a, b, arr):
	ans = []
	for i in range(b - a + 1):
		ans.append(arr[a + i][b - i])
	return ans

def get_range(n):
	initials = []
	for i in range(n):
		initials.append((0, i))
	for i in range(1, n):
		initials.append((i, n - 1))
	return initials

class Solution:

	def matrixDiagonally(self, mat):
		initials = get_range(len(mat))
		ans = []
		lvl = 0
		for i in initials:
			(a, b) = i
			temp = level_range(a, b, mat)
			if lvl % 2 == 0:
				ans += temp[::-1]
			else:
				ans += temp
			lvl += 1
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		dic = {}
		for i in range(len(mat)):
			for j in range(len(mat[0])):
				t = i + j
				if t not in dic:
					dic[t] = []
				dic[t].append(mat[i][j])
		res = []
		for k in dic:
			if k % 2 == 0:
				res.extend(dic[k][::-1])
			else:
				res.extend(dic[k])
		return res


class Solution:

	def matrixDiagonally(self, mat):
		mp = dict()
		n = len(mat)
		for i in range(n):
			for j in range(n):
				if i + j in mp:
					mp[i + j].append(mat[i][j])
				else:
					mp[i + j] = [mat[i][j]]
		lst = []
		for (k, v) in mp.items():
			if k % 2 == 0:
				v.reverse()
				lst = lst + v
			else:
				lst = lst + v
		return lst


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		s = [[] for i in range(2 * n - 1)]
		for i in range(n):
			for j in range(n):
				m = i + j
				if m % 2 == 1:
					s[m].append(mat[i][j])
				else:
					s[m].insert(0, mat[i][j])
		l = []
		for i in s:
			l.extend(i)
		return l


class Solution:

	def matrixDiagonally(self, mat):
		out = []
		(i, j) = (0, 0)
		up = True
		n = len(mat)
		while i < n and j < n:
			if up:
				while i > 0 and j < n - 1:
					out.append(mat[i][j])
					i -= 1
					j += 1
				out.append(mat[i][j])
				if j == n - 1:
					i += 1
				else:
					j += 1
			else:
				while j > 0 and i < n - 1:
					out.append(mat[i][j])
					j -= 1
					i += 1
				out.append(mat[i][j])
				if i == n - 1:
					j += 1
				else:
					i += 1
			up = not up
		return out


class Solution:

	def matrixDiagonally(self, mat):
		if not mat or not mat[0]:
			return []
		(N, M) = (len(mat), len(mat[0]))
		(row, column) = (0, 0)
		direction = 1
		result = []
		while row < N and column < M:
			result.append(mat[row][column])
			new_row = row + (-1 if direction == 1 else 1)
			new_column = column + (1 if direction == 1 else -1)
			if new_row < 0 or new_row == N or new_column < 0 or (new_column == M):
				if direction:
					row += column == M - 1
					column += column < M - 1
				else:
					column += row == N - 1
					row += row < N - 1
				direction = 1 - direction
			else:
				row = new_row
				column = new_column
		return result


class Solution:

	def matrixDiagonally(self, mat):
		m = len(mat)
		r = 0
		c = 0
		k = 0
		isUp = True
		result = []
		while k < m * m:
			if isUp:
				while r >= 0 and c < m:
					result.append(mat[r][c])
					r -= 1
					c += 1
					k += 1
				if r < 0 and c <= m - 1:
					r = 0
				if c == m:
					r = r + 2
					c -= 1
			else:
				while r < m and c >= 0:
					result.append(mat[r][c])
					r += 1
					c -= 1
					k += 1
				if c < 0 and r <= m - 1:
					c = 0
				if r == m:
					c = c + 2
					r -= 1
			isUp = not isUp
		return result
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[0])] for j in range(n[0])]
		k = 0
		for i in range(n[0]):
			for j in range(n[0]):
				matrix[i][j] = arr[k]
				k += 1
		a = Solution().matrixDiagonally(matrix)
		for x in a:
			print(x, end=' ')
		print('')


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat[0])
		if n == 1:
			return mat[0]
		ans = []
		for e in range(n):
			r = e
			c = 0
			temp = []
			for x in range(e + 1):
				temp.append(mat[r][c])
				r -= 1
				c += 1
			if e % 2 == 1:
				temp.reverse()
			ans = ans + temp
		cl = 1
		for e in range(n - 1, 0, -1):
			r = n - 1
			c = cl
			temp = []
			for x in range(e):
				temp.append(mat[r][c])
				r -= 1
				c += 1
			if e % 2 == 0:
				temp.reverse()
			ans = ans + temp
			cl += 1
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		i = 0
		j = 0
		k = 0
		n = len(mat)
		isUp = True
		while k < n * n:
			if isUp:
				while i >= 0 and j < n:
					print(mat[i][j], end=' ')
					k += 1
					j += 1
					i -= 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					j -= 1
					i += 2
			else:
				while j >= 0 and i < n:
					print(mat[i][j], end=' ')
					k += 1
					i += 1
					j -= 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					i -= 1
					j += 2
			isUp = not isUp
		return []


from collections import deque

class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		i = 0
		j = 0
		k = 0
		up = True
		res = deque()
		while k < n * n:
			if up:
				while i >= 0 and j < n:
					res.append(mat[i][j])
					i -= 1
					j += 1
					k += 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i += 2
					j -= 1
			else:
				while j >= 0 and i < n:
					res.append(mat[i][j])
					i += 1
					j -= 1
					k += 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j += 2
					i -= 1
			up = not up
		return res


class Solution:

	def matrixDiagonally(n, mat):
		result = []
		rows = len(mat)
		cols = len(mat[0])
		num_of_diags = rows + cols - 1
		for diag in range(num_of_diags):
			if diag % 2 == 0:
				i = min([diag, rows - 1])
				j = diag - i
				while i > -1 and j < cols:
					result.append(mat[i][j])
					i -= 1
					j += 1
			else:
				j = min([diag, cols - 1])
				i = diag - j
				while j > -1 and i < rows:
					result.append(mat[i][j])
					i += 1
					j -= 1
		return result


class Solution:

	def matrixDiagonally(self, mat):
		i = 0
		j = 0
		counter = 0
		isUp = True
		n = len(mat)
		result = []
		while counter < n * n:
			if isUp:
				while i >= 0 and j < n:
					result.append(mat[i][j])
					counter += 1
					j += 1
					i -= 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i = i + 2
					j -= 1
			else:
				while j >= 0 and i < n:
					result.append(mat[i][j])
					counter += 1
					i += 1
					j -= 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j = j + 2
					i -= 1
			isUp = not isUp
		return result


class Solution:

	def __init__(self):
		self.r = []
		self.n = 0

	def matrixDiagonally(self, a):
		self.r = []
		self.n = len(a)
		self.traverseDiagonalUp(a, 0, 0)
		return self.r

	def traverseDiagonalUp(self, a, x, y):
		i = x
		j = y
		while self.n > j > -1 and -1 < i < self.n:
			self.r.append(a[i][j])
			i -= 1
			j += 1
		if j == self.n:
			self.traverseDiagonalDown(a, i + 2, j - 1)
		elif i == -1:
			self.traverseDiagonalDown(a, i + 1, j)

	def traverseDiagonalDown(self, a, x, y):
		i = x
		j = y
		while self.n > j > -1 and -1 < i < self.n:
			self.r.append(a[i][j])
			i += 1
			j -= 1
		if i == self.n:
			self.traverseDiagonalUp(a, i - 1, j + 2)
		elif j == -1:
			self.traverseDiagonalUp(a, i, j + 1)


class Solution:

	def matrixDiagonally(self, mat):
		res = []
		i = 0
		row = 0
		col = 0
		flag = True
		n = len(mat)
		while row < n and col < n:
			if flag:
				while row > 0 and col < n - 1:
					res.append(mat[row][col])
					row -= 1
					col += 1
				res.append(mat[row][col])
				if col == n - 1:
					row += 1
				else:
					col += 1
			else:
				while col > 0 and row < n - 1:
					res.append(mat[row][col])
					row += 1
					col -= 1
				res.append(mat[row][col])
				if row == n - 1:
					col += 1
				else:
					row += 1
			flag = not flag
		return res


class Solution:

	def matrixDiagonally(self, mat):
		dia = []
		n = len(mat)
		sum = 0
		while sum <= 2 * (n - 1):
			if sum < n:
				a = sum
				b = 0
				while a >= 0:
					if sum % 2 == 0:
						dia.append(mat[a][b])
					else:
						dia.append(mat[b][a])
					a -= 1
					b += 1
			else:
				a = n - 1
				b = sum - n + 1
				while a >= sum - n + 1:
					if sum % 2 == 0:
						dia.append(mat[a][b])
					else:
						dia.append(mat[b][a])
					a -= 1
					b += 1
			sum += 1
		return dia


class Solution:

	def matrixDiagonally(self, mat):
		returnArray = []
		rowNumber = 0
		colNumber = 0
		numRowsCols = len(mat)
		isUp = True
		stop = False
		returnArray.append(mat[rowNumber][colNumber])
		while not stop:
			while not isUp:
				if rowNumber + 1 < numRowsCols and colNumber - 1 > -1:
					rowNumber += 1
					colNumber -= 1
				elif rowNumber + 1 < numRowsCols:
					rowNumber += 1
					isUp = True
				elif colNumber + 1 < numRowsCols:
					colNumber += 1
					isUp = True
				returnArray.append(mat[rowNumber][colNumber])
			while isUp:
				if rowNumber - 1 > -1 and colNumber + 1 < numRowsCols:
					rowNumber -= 1
					colNumber += 1
				elif colNumber + 1 < numRowsCols:
					colNumber += 1
					isUp = False
				elif rowNumber + 1 < numRowsCols:
					rowNumber += 1
					isUp = False
				else:
					stop = True
					isUp = False
				if not stop:
					returnArray.append(mat[rowNumber][colNumber])
		return returnArray


class Solution:

	def matrixDiagonally(self, mat):
		i = 0
		j = 0
		count = 0
		flag = 1
		ls = []
		while count < len(mat) * len(mat[0]):
			if flag == 1:
				while i >= 0 and j < len(mat[0]):
					ls.append(mat[i][j])
					i -= 1
					j += 1
					count += 1
				if i < 0 and j <= len(mat[0]) - 1:
					i = 0
				if j == len(mat[0]):
					j -= 1
					i += 2
			else:
				while i < len(mat) and j >= 0:
					ls.append(mat[i][j])
					i += 1
					j -= 1
					count += 1
				if j < 0 and i <= len(mat) - 1:
					j = 0
				if i == len(mat):
					i -= 1
					j += 2
			flag = 1 if flag == 0 else 0
		return ls


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		i = 0
		j = 0
		k = 0
		lst = []
		up = True
		while k < n * n:
			if up:
				while i >= 0 and j < n:
					lst.append(mat[i][j])
					k += 1
					i -= 1
					j += 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i = i + 2
					j -= 1
			else:
				while i < n and j >= 0:
					lst.append(mat[i][j])
					k += 1
					j -= 1
					i += 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j = j + 2
					i -= 1
			up = not up
		return lst


class Solution:

	def matrixDiagonally(self, matrix):
		d = {}
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				if i + j not in d:
					d[i + j] = [matrix[i][j]]
				else:
					d[i + j].append(matrix[i][j])
		ans = []
		for (k, v) in d.items():
			if k % 2 == 0:
				ans.extend(v[::-1])
			else:
				ans.extend(v)
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		numRows = len(mat)
		numCols = len(mat[0])
		diagonals = [[] for _ in range(numRows + numCols - 1)]
		for r in range(numRows):
			for c in range(numCols):
				diagonals[r + c].append(mat[r][c])
		res = []
		res = diagonals[0]
		for x in range(1, len(diagonals)):
			if x % 2:
				res.extend(diagonals[x])
			else:
				res.extend(diagonals[x][::-1])
		return res


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		if n == 1:
			return [mat[0][0]]
		up = False
		(i, j) = (0, 0)
		res = [mat[0][0]]
		while len(res) < len(mat) * len(mat[0]):
			if up:
				if i == n - 1:
					j += 1
				else:
					i += 1
				while i >= 0 and j < n:
					res.append(mat[i][j])
					i -= 1
					j += 1
				i += 1
				j -= 1
				up = False
			else:
				if j == n - 1:
					i += 1
				else:
					j += 1
				while i < n and j >= 0:
					res.append(mat[i][j])
					i += 1
					j -= 1
				i -= 1
				j += 1
				up = True
		return res


class Solution:

	def matrixDiagonally(self, mat):
		output = []
		n = len(mat)
		col = 0
		row = 0
		up = True
		while row < n and col < n:
			if up:
				while row > 0 and col < n - 1:
					output.append(mat[row][col])
					row -= 1
					col += 1
				output.append(mat[row][col])
				if col == n - 1:
					row += 1
				else:
					col += 1
			else:
				while col > 0 and row < n - 1:
					output.append(mat[row][col])
					row += 1
					col -= 1
				output.append(mat[row][col])
				if row == n - 1:
					col += 1
				else:
					row += 1
			up = not up
		return output


class Solution:

	def matrixDiagonally(self, mat):
		r = len(mat)
		c = len(mat[0])
		diag = []
		check_revers = False
		for k in range(r):
			i = k
			j = 0
			l = []
			while i >= 0:
				l.append(mat[i][j])
				i -= 1
				j += 1
			if check_revers == False:
				check_revers = True
			else:
				l.reverse()
				check_revers = False
			for ll in l:
				diag.append(ll)
		for k in range(1, c):
			i = r - 1
			j = k
			l = []
			while j < c:
				l.append(mat[i][j])
				i -= 1
				j += 1
			if check_revers == False:
				check_revers = True
			else:
				l.reverse()
				check_revers = False
			for ll in l:
				diag.append(ll)
		return diag


class Solution:

	def matrixDiagonally(self, m):
		ans = []
		r = len(m)
		c = len(m[0])
		lst = [[] for i in range(r * c)]
		for i in range(r):
			for j in range(c):
				if (i + j) % 2 != 0:
					lst[i + j].append(m[i][j])
				else:
					lst[i + j].insert(0, m[i][j])
		for arr in lst:
			for x in arr:
				ans.append(x)
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		i = 0
		j = 0
		k = 0
		isup = 1
		result_list = []
		while k < n[0] * n[0]:
			if isup:
				while i >= 0 and j < n[0]:
					result_list.append(mat[i][j])
					k += 1
					j += 1
					i -= 1
				if i < 0 and j < n[0]:
					i = 0
				if j == n[0]:
					i = i + 2
					j -= 1
			else:
				while j >= 0 and i < n[0]:
					result_list.append(mat[i][j])
					k += 1
					i += 1
					j -= 1
				if j < 0 and i <= n[0] - 1:
					j = 0
				if i == n[0]:
					j = j + 2
					i -= 1
			isup = not isup
		return result_list


class Solution:

	def matrixDiagonally(self, matrix):
		(num_rows, num_cols) = (len(matrix), len(matrix[0]))
		diagonals = [[] for _ in range(num_rows + num_cols - 1)]
		for i in range(num_rows):
			for j in range(num_cols):
				diagonals[i + j].append(matrix[i][j])
		res = diagonals[0]
		for x in range(1, len(diagonals)):
			if x % 2 == 1:
				res.extend(diagonals[x])
			else:
				res.extend(diagonals[x][::-1])
		return res


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		s = [[] for i in range(2 * (n - 1) + 1)]
		for i in range(n):
			for j in range(n):
				s[i + j].append(mat[i][j])
		k = len(s)
		for i in range(2, k):
			if i % 2 == 0:
				s[i] = s[i][::-1]
		res = []
		for i in s:
			res.extend(i)
		return res


class Solution:

	def matrixDiagonally(self, mat):
		h = {}
		n = len(mat)
		for i in range(2 * n - 1):
			h[i] = []
		for i in range(n):
			for j in range(n):
				h[i + j].append(mat[i][j])
		res = []
		for i in h:
			if i % 2 == 0:
				res = res + h[i][::-1]
			else:
				res = res + h[i]
		return res


class Solution:

	def traverseUp(self, i, j, mat):
		res = []
		n = i
		while j <= n:
			res.append(mat[i][j])
			i -= 1
			j += 1
		return res

	def traverseDown(self, i, j, mat):
		res = []
		n = i
		temp = j
		j = i
		i = temp
		while i <= n:
			res.append(mat[i][j])
			i += 1
			j -= 1
		return res

	def matrixDiagonally(self, mat):
		dir = 0
		n = len(mat[0])
		res = []
		for row in range(n):
			if dir == 0:
				res += self.traverseUp(row, 0, mat)
				dir = 1
			else:
				res += self.traverseDown(row, 0, mat)
				dir = 0
		for col in range(1, n):
			if dir == 0:
				res += self.traverseUp(n - 1, col, mat)
				dir = 1
			else:
				res += self.traverseDown(n - 1, col, mat)
				dir = 0
		return res


class Solution:

	def matrixDiagonally(self, mat):
		a = []
		row = 0
		col = 0
		n = len(mat)
		for i in range(n * n):
			a.append(mat[row][col])
			if (row + col) % 2 == 0:
				if col == n - 1:
					row += 1
				elif row == 0:
					col += 1
				else:
					row -= 1
					col += 1
			elif row == n - 1:
				col += 1
			elif col == 0:
				row += 1
			else:
				row += 1
				col -= 1
		return a


class Solution:

	def matrixDiagonally(self, mat):
		r = len(mat)
		c = len(mat[0])
		i = 0
		j = 0
		res = []
		f = -1
		while i < r:
			f *= -1
			ni = i
			nj = j
			t = []
			while ni >= 0 and nj < c:
				t.append(mat[ni][nj])
				ni -= 1
				nj += 1
			if f == 1:
				res.extend(t)
			else:
				res.extend(t[::-1])
			i += 1
		i -= 1
		j += 1
		while j < c:
			f *= -1
			ni = i
			nj = j
			t = []
			while ni >= 0 and nj < c:
				t.append(mat[ni][nj])
				ni -= 1
				nj += 1
			if f == 1:
				res.extend(t)
			else:
				res.extend(t[::-1])
			j += 1
		return res


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		i = j = k = 0
		isup = True
		lis = []
		while k < n * n:
			if isup:
				while i >= 0 and j < n:
					lis.append(mat[i][j])
					k += 1
					j += 1
					i -= 1
				if i < 0 and j <= n - 1:
					i = 0
				if j == n:
					i += 2
					j -= 1
			else:
				while j >= 0 and i < n:
					lis.append(mat[i][j])
					k += 1
					i += 1
					j -= 1
				if j < 0 and i <= n - 1:
					j = 0
				if i == n:
					j += 2
					i -= 1
			isup = not isup
		return lis


class Solution:

	def matrixDiagonally(self, mat):
		res = []
		n = len(mat)
		i = 0
		j = 0
		res.append(mat[i][j])
		while i != n - 1 or j != n - 1:
			if j + 1 < n:
				j = j + 1
			else:
				i = i + 1
			while True:
				res.append(mat[i][j])
				if i + 1 >= n or j - 1 <= -1:
					break
				i = i + 1
				j = j - 1
			if i + 1 < n:
				i = i + 1
			else:
				j = j + 1
			while True:
				res.append(mat[i][j])
				if i - 1 <= -1 or j + 1 >= n:
					break
				i = i - 1
				j = j + 1
		return res


from collections import defaultdict

class Solution:

	def matrixDiagonally(self, mat):
		d = defaultdict(list)
		for i in range(len(matrix)):
			for j in range(len(matrix[i])):
				d[i + j].append(matrix[i][j])
		ans = []
		for (k, v) in d.items():
			if k % 2 == 0:
				ans.extend(v[::-1])
			else:
				ans.extend(v)
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		up = 1
		n = len(mat)
		(i, j) = (0, 0)
		lst = []
		for _ in range(n * n):
			lst.append(mat[i][j])
			if up:
				if i - 1 >= 0 and j + 1 < n:
					i = i - 1
					j = j + 1
				elif j + 1 < n:
					j += 1
					up = 0
				else:
					i += 1
					up = 0
			elif i + 1 < n and j - 1 >= 0:
				i = i + 1
				j = j - 1
			elif i + 1 < n:
				i += 1
				up = 1
			else:
				j += 1
				up = 1
		return lst


class Solution:

	def matrixDiagonally(self, mat):
		flag = False
		ans = []
		k = 0
		r = len(mat)
		c = len(mat[0])
		while k < r:
			i = 0
			j = k
			l = []
			while i < r and j >= 0:
				l.append(mat[i][j])
				i += 1
				j -= 1
			if not flag:
				l.reverse()
			ans.extend(l)
			flag = not flag
			k += 1
		k = 1
		while k < c:
			i = k
			j = c - 1
			l = []
			while i < r and j >= 0:
				l.append(mat[i][j])
				i += 1
				j -= 1
			if not flag:
				l.reverse()
			ans.extend(l)
			flag = not flag
			k += 1
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		m = len(mat)
		n = len(mat[0])
		result = []
		rev = True

		def traverse(r, c, result, rev):
			l = []
			while r < m and c >= 0:
				l.append(mat[r][c])
				r += 1
				c -= 1
			if not rev:
				result += l
			else:
				result += l[::-1]
			return not rev
		for c in range(n):
			rev = traverse(0, c, result, rev)
		for r in range(1, m):
			rev = traverse(r, n - 1, result, rev)
		return result


class Solution:

	def matrixDiagonally(self, mat):
		arr = []
		for i in range(2 * len(mat) - 1):
			arr.append([])
		for i in range(len(mat)):
			for j in range(len(mat)):
				arr[i + j].append(mat[i][j])
		ans = []
		i = 0
		n = len(arr)
		turn = 0
		while i < n:
			if i % 2 == 0:
				arr[i].reverse()
				for j in arr[i]:
					ans.append(j)
				i += 1
			else:
				for j in range(len(arr[i])):
					ans.append(arr[i][j])
				i += 1
		return ans


class Solution:

	def matrixDiagonally(self, mat):
		i = 0
		j = 0
		nodes_traversed = 0
		total_nodes = len(mat) * len(mat)
		isUp = True
		res = []
		while nodes_traversed < total_nodes:
			if isUp:
				while i >= 0 and j < len(mat):
					res.append(mat[i][j])
					nodes_traversed += 1
					i -= 1
					j += 1
				if i < 0 and j <= len(mat) - 1:
					i = 0
				if j == len(mat):
					i = i + 2
					j -= 1
			else:
				while j >= 0 and i < len(mat):
					res.append(mat[i][j])
					nodes_traversed += 1
					i += 1
					j -= 1
				if j < 0 and i <= len(mat) - 1:
					j = 0
				if i == len(mat):
					j = j + 2
					i -= 1
			isUp = not isUp
		return res


class Solution:

	def matrixDiagonally(self, mat):
		n = len(mat)
		res = []
		for l in range(2 * (n - 1) + 1):
			if l % 2 == 0:
				i = min(l, n - 1)
				j = l - i
			else:
				j = min(l, n - 1)
				i = l - j
			while i >= 0 and j >= 0 and (i < n) and (j < n):
				res.append(mat[i][j])
				if l % 2 == 0:
					i -= 1
					j += 1
				else:
					i += 1
					j -= 1
		return res


class Solution:

	def matrixDiagonally(self, arr):
		n = len(arr)
		ans = []
		mode = 0
		it = 0
		lower = 0
		for t in range(2 * n - 1):
			t1 = t
			if t1 >= n:
				mode += 1
				t1 = n - 1
				it -= 1
				lower += 1
			else:
				lower = 0
				it += 1
			for i in range(t1, lower - 1, -1):
				if (t1 + mode) % 2 == 0:
					ans.append(arr[i][t1 + lower - i])
				else:
					ans.append(arr[t1 + lower - i][i])
		return ans


from collections import deque

class Solution:

	def matrixDiagonally(n, mat):
		n = len(mat)
		if n < 2:
			return mat[0]
		temp = list()
		for i in range(1, n):
			coords = []
			x = list(range(0, i + 1))
			y = [-1 * var + i for var in x]
			if len(x) > 1:
				for k in range(len(x)):
					coords.append(mat[x[k]][y[k]])
			temp.append(coords)
		for j in range(n - 1, -1, -1):
			coords = []
			x = list(range(n - 1, n - 1 - j, -1))
			y = x.copy()
			y.reverse()
			if len(y) > 1:
				for k in range(len(y)):
					coords.append(mat[y[k]][x[k]])
			temp.append(coords)
		diag = []
		result = deque()
		for k in range(len(temp)):
			arr = temp[k].copy()
			if k % 2 != 0:
				arr.reverse()
			diag.append(arr)
			for l in range(len(diag[k])):
				result.append(diag[k][l])
		result.appendleft(mat[0][0])
		result.append(mat[-1][-1])
		return result


class Solution:

	def matrixDiagonally(a, mat):
		lis = [mat[0][0]]
		i = 0
		j = 0
		k = 0
		n = len(mat)
		d = False
		down = True
		while k < n * n:
			if i == n - 1 and j == n - 1:
				break
			if d:
				if down:
					while i > 0 and j < n - 1:
						k += 1
						i -= 1
						j += 1
						lis.append(mat[j][i])
				else:
					while i < n - 1 and j > 0:
						k += 1
						i += 1
						j -= 1
						lis.append(mat[j][i])
				d = False
			else:
				if i == 0:
					if j == 0:
						i += 1
						down = True
					elif j < n - 1:
						j += 1
						down = False
					else:
						i += 1
						down = False
				elif j == 0:
					if i < n - 1:
						i += 1
						down = True
					else:
						j += 1
						down = True
				elif i == n - 1:
					j += 1
					down = True
				elif j == n - 1:
					i += 1
					down = False
				lis.append(mat[j][i])
				k += 1
				d = True
		return lis