Given an NxM 2D matrix, rearrange such that 
Each diagonal in the lower left triangle of the rectangular grid is sorted in ascending order. 
Each diagonal in the upper right triangle of the rectangular grid is sorted in descending order. 
The major diagonal in the grid starting from the top-left corner is not rearranged. 
Example 1:
Input:
N = 4, M = 5 
matrix = {{3 6 3 8 2},
          {4 1 9 5 9},
          {5 7 2 4 8},
          {8 3 1 7 6}}
Output:
3 9 8 9 2
1 1 6 5 8
3 4 2 6 3
8 5 7 7 4
Explanation:
Before:
After:
Your Task:
You don't need to read input or print anything. Your task is to complete the function diagonalSort() which takes the matrix, n and m as input parameter and rearranges the elements of the matrix.
Expected Time Complexity: O(NxM)
Expected Auxiliary Space: O(N+M)
Constraints:
1 <= N,M <= 10^{4 }, 1<=N*M<=10^{5}
1 <= matrix[i] <= 10^{3}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Matrices

Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def diagonalSort(self, matrix, n, m):
        # code here 

Solutions:
class Solution:

	def diagonalSort(self, matrix, n, m):
		dict = {}
		for i in range(n):
			for j in range(m):
				if not i - j in dict:
					dict[i - j] = [matrix[i][j]]
				else:
					dict[i - j].append(matrix[i][j])
		for (k, v) in dict.items():
			if k > 0:
				v.sort(reverse=True)
			elif k < 0:
				v.sort()
			else:
				v[:] = v[::-1]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = dict[i - j].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		des = {}
		acs = {}
		dig = []
		for i in range(n):
			for j in range(m):
				if i == j:
					dig.append(matrix[i][j])
				elif i > j:
					if i - j not in acs:
						acs[i - j] = [matrix[i][j]]
					else:
						acs[i - j].append(matrix[i][j])
				elif j - i not in des:
					des[j - i] = [matrix[i][j]]
				else:
					des[j - i].append(matrix[i][j])
		for i in acs:
			acs[i].sort()
		for i in des:
			des[i].sort()
			des[i] = des[i][::-1]
		for i in range(n):
			for j in range(m):
				if i == j:
					matrix[i][j] = dig.pop(0)
				elif i > j:
					matrix[i][j] = acs[i - j].pop(0)
				else:
					matrix[i][j] = des[j - i].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, matrix, N, M):
		orgi = 1
		i = 1
		j = 0
		for i in range(1, N - 1):
			k = i
			j = 0
			arr = []
			while k < N and j < M:
				arr.append(matrix[k][j])
				k += 1
				j += 1
			arr.sort()
			k = i
			j = 0
			l = 0
			while k < N and j < M and (l < len(arr)):
				matrix[k][j] = arr[l]
				k += 1
				j += 1
				l += 1
		i = 0
		j = 1
		for j in range(1, M - 1):
			k = j
			i = 0
			arr = []
			while k < M and i < N:
				arr.append(matrix[i][k])
				k += 1
				i += 1
			arr.sort(reverse=True)
			k = j
			i = 0
			l = 0
			while k < M and i < N and (l < len(arr)):
				matrix[i][k] = arr[l]
				k += 1
				i += 1
				l += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for j in range(1, m):
			arr = []
			i = 0
			k = j
			while k < m and i < n:
				arr.append(matrix[i][k])
				k += 1
				i += 1
			arr.sort()
			i = 0
			k = j
			while k < m and i < n:
				matrix[i][k] = arr.pop()
				i += 1
				k += 1
		for i in range(1, n):
			arr = []
			j = 0
			k = i
			while k < n and j < m:
				arr.append(matrix[k][j])
				j += 1
				k += 1
			arr.sort(reverse=True)
			j = 0
			k = i
			while k < n and j < m:
				matrix[k][j] = arr.pop()
				j += 1
				k += 1
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		d = defaultdict(list)
		for i in range(n):
			for j in range(m):
				d[i - j].append(matrix[i][j])
		for i in d:
			if i > 0:
				d[i].sort()
			elif i < 0:
				d[i].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				matrix[i][j] = d[i - j][0]
				d[i - j].pop(0)


class Solution:

	def diagonalSort(self, matrix, n, m):
		for k in range(1, n):
			j = 0
			i = k
			arr1 = []
			while i < n and j < m:
				arr1.append(matrix[i][j])
				i += 1
				j += 1
			arr1.sort()
			j = 0
			i = k
			while i < n and j < m:
				matrix[i][j] = arr1[j]
				i += 1
				j += 1
		for k in range(1, m):
			j = k
			i = 0
			arr1 = []
			while i < n and j < m:
				arr1.append(matrix[i][j])
				i += 1
				j += 1
			arr1.sort(reverse=True)
			j = k
			i = 0
			while i < n and j < m:
				matrix[i][j] = arr1[i]
				i += 1
				j += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for j in range(1, m):
			items = []
			for i in range(min(n, m - j)):
				items.append(matrix[i][i + j])
			items.sort(reverse=True)
			for i in range(min(n, m - j)):
				matrix[i][i + j] = items[i]
		for i in range(1, n):
			items = []
			for j in range(min(m, n - i)):
				items.append(matrix[i + j][j])
			items.sort()
			for j in range(min(m, n - i)):
				matrix[i + j][j] = items[j]
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		if n == 1 or m == 1:
			return matrix
		for j in range(1, m):
			r = 0
			c = j
			temp = []
			while r < n and c < m:
				temp.append(matrix[r][c])
				r += 1
				c += 1
			temp.sort(reverse=True)
			r = 0
			c = j
			ind = 0
			while r < n and c < m:
				matrix[r][c] = temp[ind]
				r += 1
				c += 1
				ind += 1
		for i in range(1, n):
			r = i
			c = 0
			temp = []
			while r < n and c < m:
				temp.append(matrix[r][c])
				r += 1
				c += 1
			temp.sort()
			r = i
			c = 0
			ind = 0
			while r < n and c < m:
				matrix[r][c] = temp[ind]
				r += 1
				c += 1
				ind += 1
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		if not matrix:
			return
		if m <= 2 and n <= 2:
			return matrix
		dp = defaultdict(list)
		for i in range(n):
			for j in range(m):
				if i != j:
					dp[i - j].append(matrix[i][j])
		for k in range(-(m - 1), n):
			if k == 0:
				continue
			if k > 0:
				dp[k].sort()
			else:
				dp[k].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				if i != j:
					matrix[i][j] = dp[i - j].pop(0)
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, mat, n, m):
		mp = defaultdict(list)
		for i in range(n):
			for j in range(m):
				mp[i - j].append(mat[i][j])
		for i in range(-(m - 1), n):
			if i == 0:
				continue
			if i < 0:
				mp[i].sort(reverse=True)
			else:
				mp[i].sort()
		for i in range(n - 1, -1, -1):
			for j in range(m - 1, -1, -1):
				mat[i][j] = mp[i - j][-1]
				mp[i - j] = mp[i - j][:-1]


from collections import defaultdict, deque

class Solution:

	def diagonalSort(self, matrix, n, m):
		d = defaultdict(lambda : [])
		for i in range(n):
			for j in range(m):
				d[i - j].append(matrix[i][j])
		for key in d.keys():
			if key < 0:
				d[key].sort(reverse=True)
			elif key > 0:
				d[key].sort()
		for i in range(n):
			for j in range(m):
				if i - j == 0:
					continue
				else:
					matrix[i][j] = d[i - j].pop(0)


class Solution:

	def diagonalSort(self, mat, n, m):
		d = {}
		for row in range(n):
			for col in range(m):
				if not d.get(row - col):
					d[row - col] = []
				d[row - col].append(mat[row][col])
		for (k, v) in d.items():
			if k < 0:
				d[k] = sorted(d[k])
			elif k > 0:
				d[k] = sorted(d[k], reverse=True)
		for row in range(n):
			for col in range(m):
				if row == col:
					continue
				mat[row][col] = d[row - col].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		lower_triangle = [[] for i in range(n)]
		upper_triangle = [[] for i in range(m)]
		major_diagonal = []
		for i in range(n):
			for j in range(m):
				if j < i:
					lower_triangle[i - j].append(matrix[i][j])
				elif j > i:
					upper_triangle[j - i].append(matrix[i][j])
				else:
					major_diagonal.append(matrix[i][j])
		for i in range(n):
			lower_triangle[i].sort()
			lower_triangle[i] = lower_triangle[i][::-1]
		for i in range(m):
			upper_triangle[i].sort()
		for i in range(n):
			for j in range(m):
				if j < i:
					d = i - j
					l = len(lower_triangle[d]) - 1
					matrix[i][j] = lower_triangle[d][l]
					lower_triangle[d].pop()
				elif j > i:
					d = j - i
					l = len(upper_triangle[d]) - 1
					matrix[i][j] = upper_triangle[d][l]
					upper_triangle[d].pop()


import collections

class Solution:

	def diagonalSort(self, matrix, n, m):
		diagonals = collections.defaultdict(list)
		for i in range(n):
			for j in range(m):
				diagonals[i - j].append(matrix[i][j])
		for i in diagonals:
			if i > 0:
				diagonals[i].sort()
			if i < 0:
				diagonals[i].sort(reverse=1)
		for i in range(n):
			for j in range(m):
				matrix[i][j] = diagonals[i - j].pop(0)


import collections

class Solution:

	def diagonalSort(self, mat, n, m):
		diagonals = collections.defaultdict(list)
		for i in range(n):
			for j in range(m):
				diagonals[i - j].append(mat[i][j])
		for k in diagonals:
			diagonals[k].sort(reverse=1)
		for i in range(n):
			for j in range(m):
				if i - j > 0:
					mat[i][j] = diagonals[i - j].pop()
				elif i - j < 0:
					mat[i][j] = diagonals[i - j].pop(0)
		return mat


class Solution:

	def fun():
		arr = matrix
		for itr in range(1, m - 1):
			mm = m - itr
			nn = n - itr - 1
			for r in range(0, nn):
				for c in (r + 1, mm):
					print('r=', r, ' c=', c)
					if arr[r][c] < arr[r + 1][c + 1]:
						t = arr[r][c]
						arr[r][c] = arr[r + 1][c + 1]
						arr[r + 1][c + 1] = t

	def diagonalSort(self, matrix, n, m):
		for itr in range(1, m - 1):
			i = 0
			j = itr
			ar = []
			while i < n and j < m:
				ar.append(matrix[i][j])
				i += 1
				j += 1
			ar.sort(reverse=True)
			i = 0
			j = itr
			while i < n and j < m:
				matrix[i][j] = ar[i]
				i += 1
				j += 1
		for itr in range(1, n - 1):
			i = itr
			j = 0
			ar = []
			while i < n and j < m:
				ar.append(matrix[i][j])
				i += 1
				j += 1
			ar.sort()
			i = itr
			j = 0
			while i < n and j < m:
				matrix[i][j] = ar[j]
				i += 1
				j += 1


class Solution:

	def diagonalSort(self, mat, n, m):
		for i in range(1, n):
			j = 0
			k = i
			l = []
			while k < n and j < m:
				l.append(mat[k][j])
				k += 1
				j += 1
			l.sort()
			k = i
			j = 0
			p = 0
			while k < n and j < m:
				mat[k][j] = l[p]
				p += 1
				j += 1
				k += 1
		for i in range(1, m):
			j = 0
			k = i
			l = []
			while k < m and j < n:
				l.append(mat[j][k])
				k += 1
				j += 1
			l.sort()
			l = l[::-1]
			k = i
			j = 0
			p = 0
			while k < m and j < n:
				mat[j][k] = l[p]
				p += 1
				j += 1
				k += 1


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		d = defaultdict(list)
		for i in range(n):
			for j in range(m):
				d[i - j].append(matrix[i][j])
		for k in d:
			if k > 0:
				d[k].sort(reverse=True)
			elif k < 0:
				d[k].sort()
			else:
				d[k] = d[k][::-1]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = d[i - j].pop()
		return matrix
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = map(int, input().strip().split())
		inputLine = list(map(int, input().strip().split()))
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = inputLine[i * m + j]
		ob = Solution()
		ob.diagonalSort(matrix, n, m)
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()
		tc -= 1


class Solution:

	def diagonalSort(self, mat, m, n):
		for i in range(1, m):
			j = i
			k = 0
			li = []
			while j < m and k < n:
				li.append(mat[j][k])
				j += 1
				k += 1
			li.sort()
			j = i
			k = 0
			l = 0
			while j < m and k < n:
				mat[j][k] = li[l]
				j += 1
				k += 1
				l += 1
		for i in range(1, n):
			j = 0
			k = i
			li = []
			while j < m and k < n:
				li.append(mat[j][k])
				j += 1
				k += 1
			li.sort()
			h = len(li)
			j = 0
			k = i
			l = h - 1
			while j < m and k < n:
				mat[j][k] = li[l]
				j += 1
				k += 1
				l -= 1
		return mat
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = map(int, input().strip().split())
		inputLine = list(map(int, input().strip().split()))
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = inputLine[i * m + j]
		ob = Solution()
		ob.diagonalSort(matrix, n, m)
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()
		tc -= 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for i in range(1, m):
			j = 0
			arr = []
			while j + i < m and j < n:
				arr.append(matrix[j][j + i])
				j += 1
			arr.sort(reverse=True)
			j = 0
			while j + i < m and j < n:
				matrix[j][j + i] = arr[j]
				j += 1
		for i in range(1, n):
			j = 0
			arr = []
			while j + i < n and j < m:
				arr.append(matrix[j + i][j])
				j += 1
			arr.sort()
			j = 0
			while j + i < n and j < m:
				matrix[j + i][j] = arr[j]
				j += 1
		return matrix
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = map(int, input().strip().split())
		inputLine = list(map(int, input().strip().split()))
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = inputLine[i * m + j]
		ob = Solution()
		ob.diagonalSort(matrix, n, m)
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()
		tc -= 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		d = dict()
		for i in range(1, n):
			d[i] = []
		for i in range(1, m):
			d[-i] = []
		for i in range(n):
			for j in range(m):
				if i == j:
					continue
				elif i > j:
					d[i - j].append(matrix[i][j])
				else:
					d[i - j].append(matrix[i][j])
		for i in d.keys():
			if i < 0:
				d[i].sort()
			else:
				d[i].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				if i == j:
					continue
				elif i > j:
					matrix[i][j] = d[i - j].pop()
				else:
					matrix[i][j] = d[i - j].pop()
		return matrix
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = map(int, input().strip().split())
		inputLine = list(map(int, input().strip().split()))
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = inputLine[i * m + j]
		ob = Solution()
		ob.diagonalSort(matrix, n, m)
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()
		tc -= 1


class Solution:

	def sortFirstHalf(self, matrix, n, m):
		(start, gap) = (n - 1, n - 1)
		while gap > 0:
			temp = []
			i = start
			while i < n and i - gap < m:
				temp.append(matrix[i][i - gap])
				i += 1
			temp.sort()
			i = start
			while i < n and i - gap < m:
				matrix[i][i - gap] = temp.pop(0)
				i += 1
			gap -= 1
			start -= 1
		return matrix

	def sortSecondHalf(self, matrix, n, m):
		cnt = 0
		(start, gap) = (0, 1)
		while gap < m:
			temp = []
			i = start
			while i < n and i + gap < m:
				temp.append(matrix[i][i + gap])
				i += 1
			temp.sort(reverse=True)
			i = start
			while i < n and i + gap < m:
				matrix[i][i + gap] = temp.pop(0)
				i += 1
			gap += 1

	def diagonalSort(self, matrix, n, m):
		matrix = self.sortFirstHalf(matrix, n, m)
		matrix = self.sortSecondHalf(matrix, n, m)
		return matrix
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		(n, m) = map(int, input().strip().split())
		inputLine = list(map(int, input().strip().split()))
		matrix = [[0 for j in range(m)] for i in range(n)]
		for i in range(n):
			for j in range(m):
				matrix[i][j] = inputLine[i * m + j]
		ob = Solution()
		ob.diagonalSort(matrix, n, m)
		for i in range(n):
			for j in range(m):
				print(matrix[i][j], end=' ')
			print()
		tc -= 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		return rt(matrix)

def rt(m):
	for i in range(1, len(m[0])):
		p = []
		v = i
		j = 0
		while 0 <= v < len(m[0]) and 0 <= j < len(m):
			p.append(m[j][v])
			v += 1
			j += 1
		j = 0
		p.sort(reverse=True)
		r = 0
		v = i
		while 0 <= v < len(m[0]) and 0 <= j < len(m):
			m[j][v] = p[r]
			j += 1
			v += 1
			r += 1
	for i in range(1, len(m)):
		p = []
		v = i
		j = 0
		while 0 <= v < len(m) and 0 <= j < len(m[0]):
			p.append(m[v][j])
			v += 1
			j += 1
		j = 0
		r = 0
		v = i
		p.sort()
		while 0 <= v < len(m) and 0 <= j < len(m[0]):
			m[v][j] = p[r]
			j += 1
			v += 1
			r += 1
	return m


class Solution:

	def diagonalSort(self, matrix, n, m):
		for i in range(1, m):
			row = 0
			col = i
			x = []
			while row < n and col < m:
				x.append(matrix[row][col])
				row += 1
				col += 1
			x.sort(reverse=True)
			row = 0
			col = i
			for j in x:
				matrix[row][col] = j
				row += 1
				col += 1
		for i in range(1, n):
			x = []
			row = i
			col = 0
			while row < n and col < m:
				x.append(matrix[row][col])
				row += 1
				col += 1
			x.sort()
			row = i
			col = 0
			for j in x:
				matrix[row][col] = j
				row += 1
				col += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for i in range(1, m):
			temp = []
			for j in range(n):
				if i + j < m:
					temp.append(matrix[j][i + j])
			temp.sort(reverse=True)
			for j in range(n):
				if i + j < m:
					matrix[j][i + j] = temp[j]
		for i in range(1, n):
			temp = []
			for j in range(m):
				if i + j < n:
					temp.append(matrix[j + i][j])
			temp.sort()
			for j in range(m):
				if i + j < n:
					matrix[j + i][j] = temp[j]


class Solution:

	def diagonalSort(self, matrix, n, m):
		positiveDiff = [[] for i in range(m)]
		negativeDiff = [[] for j in range(n)]
		for i in range(n):
			for j in range(m):
				if i != j:
					if j > i:
						positiveDiff[j - i].append(matrix[i][j])
					else:
						negativeDiff[i - j].append(matrix[i][j])
		for i in range(m):
			positiveDiff[i].sort()
		for i in range(n):
			negativeDiff[i].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				if i != j:
					if j > i:
						matrix[i][j] = positiveDiff[j - i].pop()
					else:
						matrix[i][j] = negativeDiff[i - j].pop()


import heapq

class Solution:

	def diagonalSort(self, matrix, n, m):
		for diag in range(1, n):
			heap = []
			r = diag
			c = 0
			while r < n and c < m:
				heapq.heappush(heap, matrix[r][c])
				r += 1
				c += 1
			r = diag
			c = 0
			while r < n and c < m:
				matrix[r][c] = heapq.heappop(heap)
				r += 1
				c += 1
		for diag in range(1, m):
			heap = []
			r = 0
			c = diag
			while c < m and r < n:
				heapq.heappush(heap, -matrix[r][c])
				r += 1
				c += 1
			r = 0
			c = diag
			while c < m and r < n:
				matrix[r][c] = -heapq.heappop(heap)
				r += 1
				c += 1


class Solution:

	def diagonalSort(self, mat, n, m):
		for x in range(1, len(mat[0])):
			(a, b) = (x, 0)
			l = []
			while a < len(mat[0]) and b < len(mat):
				l.append(mat[b][a])
				a += 1
				b += 1
			l.sort()
			l.reverse()
			a -= 1
			b -= 1
			while l:
				mat[b][a] = l.pop()
				a -= 1
				b -= 1
		for x in range(1, len(mat)):
			(a, b) = (0, x)
			l = []
			while a < len(mat[0]) and b < len(mat):
				l.append(mat[b][a])
				a += 1
				b += 1
			l.sort()
			a -= 1
			b -= 1
			while l:
				mat[b][a] = l.pop()
				a -= 1
				b -= 1


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		default_dict = defaultdict(list)
		for row in range(len(matrix)):
			for col in range(len(matrix[0])):
				default_dict[row - col].append(matrix[row][col])
		for i in default_dict:
			default_dict[i].sort()
		for row in range(len(matrix)):
			for col in range(len(matrix[0])):
				if col > row:
					matrix[row][col] = default_dict[row - col].pop()
				elif row > col:
					matrix[row][col] = default_dict[row - col].pop(0)
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		diagonalDict = defaultdict(list)
		for row in range(len(matrix)):
			for col in range(len(matrix[0])):
				diagonalDict[row - col].append(matrix[row][col])
		for key in diagonalDict:
			if key > 0:
				diagonalDict[key].sort()
			elif key < 0:
				diagonalDict[key].sort(reverse=True)
		for row in range(len(matrix) - 1, -1, -1):
			for col in range(len(matrix[0]) - 1, -1, -1):
				matrix[row][col] = diagonalDict[row - col].pop()
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		to = defaultdict(list)
		for i in range(n):
			for j in range(m):
				to[i - j].append(matrix[i][j])
		for i in to:
			if i == 0:
				continue
			elif i > 0:
				to[i].sort()
			else:
				to[i].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				matrix[i][j] = to[i - j].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		dictt = {}
		for r in range(n):
			for c in range(m):
				if r - c == 0:
					continue
				if r - c in dictt.keys():
					dictt[r - c].append(matrix[r][c])
				else:
					dictt[r - c] = [matrix[r][c]]
		for (k, v) in dictt.items():
			if k > 0:
				v.sort()
			else:
				v.sort(reverse=True)
		for r in range(n):
			for c in range(m):
				if r - c in dictt.keys():
					matrix[r][c] = dictt[r - c].pop(0)


class Solution:

	def diagonalSort(self, matrix, n, m):
		for s in range(1, n):
			tmp_list = []
			(i, j) = (s, 0)
			k = 0
			while i + k < n and j + k < m:
				tmp_list.append(matrix[i + k][j + k])
				k += 1
			tmp_list.sort()
			k = 0
			while i + k < n and j + k < m:
				matrix[i + k][j + k] = tmp_list[k]
				k += 1
		for s in range(1, m):
			(i, j) = (0, s)
			tmp_list = []
			k = 0
			while i + k < n and j + k < m:
				tmp_list.append(matrix[i + k][j + k])
				k += 1
			tmp_list.sort(key=lambda x: -1 * x)
			k = 0
			while i + k < n and j + k < m:
				matrix[i + k][j + k] = tmp_list[k]
				k += 1


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		diagonal_elements = defaultdict(list)
		for row in range(n):
			for column in range(m):
				diagonal_elements[row - column].append(matrix[row][column])
		for number_list in diagonal_elements:
			if number_list == 0:
				diagonal_elements[number_list].reverse()
			if number_list > 0:
				diagonal_elements[number_list].sort(reverse=True)
			if number_list < 0:
				diagonal_elements[number_list].sort()
		for row in range(n):
			for column in range(m):
				matrix[row][column] = diagonal_elements[row - column].pop()
		return matrix


from collections import defaultdict as dt

class Solution:

	def diagonalSort(self, matrix, n, m):
		dic = dt(list)
		for i in range(n):
			for j in range(m):
				dic[i - j].append(matrix[i][j])
		for i in dic:
			if i < 0:
				dic[i].sort()
			elif i > 0:
				dic[i].sort(reverse=True)
			else:
				dic[i].reverse()
		for i in range(n):
			for j in range(m):
				matrix[i][j] = dic[i - j].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		l = []
		r = []
		for x in range(1, n):
			lri = x
			lci = 0
			temp = []
			while lri < n and lci < m:
				temp.append(matrix[lri][lci])
				lri += 1
				lci += 1
			temp.sort()
			l.append(temp)
		for x in range(1, m):
			rri = 0
			rci = x
			temp = []
			while rri < n and rci < m:
				temp.append(matrix[rri][rci])
				rri += 1
				rci += 1
			temp.sort(reverse=True)
			r.append(temp)
		lidx = 0
		for x in range(1, n):
			lri = x
			lci = 0
			temp = l[lidx]
			j = 0
			while j < len(temp) and lri < n and (lci < m):
				matrix[lri][lci] = temp[j]
				lri += 1
				lci += 1
				j += 1
			lidx += 1
		ridx = 0
		for x in range(1, m):
			lri = 0
			lci = x
			temp = r[ridx]
			j = 0
			while j < len(temp) and lri < n and (lci < m):
				matrix[lri][lci] = temp[j]
				lri += 1
				lci += 1
				j += 1
			ridx += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for j in range(1, m):
			(x, y) = (0, j)
			v = []
			while 0 <= x < n and 0 <= y < m:
				v.append(matrix[x][y])
				x += 1
				y += 1
			v.sort(reverse=True)
			k = 0
			(x, y) = (0, j)
			while 0 <= x < n and 0 <= y < m:
				matrix[x][y] = v[k]
				x += 1
				y += 1
				k += 1
		for i in range(1, n):
			(x, y) = (i, 0)
			v = []
			while 0 <= x < n and 0 <= y < m:
				v.append(matrix[x][y])
				x += 1
				y += 1
			v.sort()
			k = 0
			(x, y) = (i, 0)
			while 0 <= x < n and 0 <= y < m:
				matrix[x][y] = v[k]
				x += 1
				y += 1
				k += 1


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		dic = defaultdict(list)
		for i in range(n):
			for j in range(m):
				dic[j - i].append(matrix[i][j])
		for k in dic.keys():
			if k > 0:
				dic[k].sort()
			if k < 0:
				dic[k].sort(reverse=True)
		for i in range(n):
			for j in range(m):
				if i == j:
					continue
				else:
					matrix[i][j] = dic[j - i].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		dict1 = {}
		for i in range(n):
			for j in range(m):
				if j - i not in dict1:
					dict1[j - i] = [matrix[i][j]]
				else:
					z = dict1[j - i]
					z.append(matrix[i][j])
		for i in dict1:
			if i != 0:
				dict1[i] = sorted(dict1[i])
		matrix.clear()
		for i in range(n):
			arr = []
			for j in range(m):
				z = j - i
				if z == 0:
					arr.append(dict1[0].pop(0))
				elif z > 0:
					arr.append(dict1[z].pop(-1))
				elif z < 0:
					arr.append(dict1[z].pop(0))
			matrix.append(arr)


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		pos = []
		neg = []
		l = defaultdict(list)
		for i in range(n):
			for j in range(m):
				l[i - j].append(matrix[i][j])
		for i in range(n):
			for j in range(m):
				if i < j:
					l[i - j].sort(reverse=True)
				if i > j:
					l[i - j].sort()
		for i in range(n):
			for j in range(m):
				matrix[i][j] = l[i - j].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		for i in range(1, n):
			x = []
			j = 0
			k = i
			while j < m and k < n:
				x.append(matrix[k][j])
				j += 1
				k += 1
			x = sorted(x)
			a = 0
			b = i
			while a < m and b < n:
				matrix[b][a] = x[a]
				a += 1
				b += 1
		high = []
		for i in range(1, m):
			x = []
			j = 0
			k = i
			while j < n and k < m:
				x.append(matrix[j][k])
				j += 1
				k += 1
			x = sorted(x, reverse=True)
			high.append(x)
			a = 0
			b = i
			while a < n and b < m:
				matrix[a][b] = x[a]
				a += 1
				b += 1
		return matrix


class Solution:

	def find(self, i, j, n, m, arr, f):
		x = i
		y = j
		tmp = []
		while x < n and y < m:
			tmp.append(arr[x][y])
			x += 1
			y += 1
		if f:
			tmp.sort(reverse=True)
		else:
			tmp.sort()
		x = i
		y = j
		for p in tmp:
			arr[x][y] = p
			x += 1
			y += 1

	def diagonalSort(self, matrix, n, m):
		for i in range(1, n):
			self.find(i, 0, n, m, matrix, 0)
		for j in range(1, m):
			self.find(0, j, n, m, matrix, 1)
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		diag = {}
		for i in range(n):
			for j in range(m):
				if i - j in diag.keys():
					diag[i - j].append(matrix[i][j])
				else:
					diag[i - j] = [matrix[i][j]]
		for i in range(n):
			for j in range(m):
				if i - j in diag.keys() and i - j != 0:
					if i - j < 0:
						diag[i - j].sort()
					else:
						diag[i - j].sort(reverse=True)
					matrix[i][j] = diag[i - j].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		from collections import defaultdict, deque
		hashmap = defaultdict(deque)
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				hashmap[j - i].append(matrix[i][j])
		for key in hashmap:
			hashmap[key] = deque(sorted(hashmap[key]))
		for i in range(len(matrix)):
			for j in range(len(matrix[0])):
				if j - i > 0:
					matrix[i][j] = hashmap[j - i].pop()
				elif j - i < 0:
					matrix[i][j] = hashmap[j - i].popleft()


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		right = defaultdict(list)
		left = defaultdict(list)
		i = 0
		while i < n:
			j = 0
			while j < m:
				if j > i:
					right[j - i].append(matrix[i][j])
				if j < i:
					left[i - j].append(matrix[i][j])
				j += 1
			i += 1
		for i in right:
			right[i].sort(reverse=True)
		for i in left:
			left[i].sort()
		for i in range(n):
			for j in range(m):
				if j > i:
					matrix[i][j] = right[j - i].pop(0)
				if i > j:
					matrix[i][j] = left[i - j].pop(0)


class Solution:

	def find(self, i, j, arr, m, n, rev):
		yt = []
		ii = i
		jj = j
		while ii < n and jj < m:
			yt.append(arr[ii][jj])
			ii += 1
			jj += 1
		if not rev:
			yt.sort(reverse=True)
		else:
			yt.sort()
		a = i
		b = j
		tmp = 0
		while a < n and b < m:
			arr[a][b] = yt[tmp]
			a += 1
			b += 1
			tmp += 1

	def diagonalSort(self, matrix, n, m):
		for i in range(1, m):
			self.find(0, i, matrix, m, n, False)
		for i in range(1, n):
			self.find(i, 0, matrix, m, n, True)


class Solution:

	def diagonalSort(self, matrix, n, m):
		i = 1
		j = 0
		while i < m:
			j = 0
			arr = sorted([matrix[j][j + i] for j in range(n) if j + i < m], reverse=True)
			for k in range(n):
				if k + i >= m:
					break
				matrix[k][k + i] = arr[k]
			i += 1
		i = 1
		j = 0
		while i < n:
			j = 0
			arr = sorted([matrix[j + i][j] for j in range(m) if j + i < n])
			for k in range(m):
				if k + i >= n:
					break
				matrix[k + i][k] = arr[k]
			i += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		for col in range(1, m):
			f = 0
			c = col
			arriba = []
			while f < n and c < m:
				arriba.append(matrix[f][c])
				f += 1
				c += 1
			arriba = sorted(arriba)
			f = 0
			c = col
			index = len(arriba) - 1
			while f < n and c < m:
				matrix[f][c] = arriba.pop()
				f += 1
				c += 1
		for fila in range(1, n):
			abajo = []
			f = fila
			c = 0
			while f < n and c < m:
				abajo.append(matrix[f][c])
				f += 1
				c += 1
			f = fila
			c = 0
			abajo = list(reversed(sorted(abajo)))
			index = 0
			while f < n and c < m:
				matrix[f][c] = abajo.pop()
				f += 1
				c += 1


def diagonalSort1(mat):
	n = len(mat)
	m = len(mat[0])
	v = list()
	for row in range(1, n):
		for (i, j) in zip(range(row, n), range(0, m)):
			v.append(mat[i][j])
		v.sort(reverse=False)
		t = 0
		for (i, j) in zip(range(row, n), range(0, m)):
			mat[i][j] = v[t]
			t += 1
		v.clear()
	for col in range(1, m):
		for (i, j) in zip(range(0, n), range(col, m)):
			v.append(mat[i][j])
		v.sort(reverse=True)
		t = 0
		for (i, j) in zip(range(0, n), range(col, m)):
			mat[i][j] = v[t]
			t += 1
		v.clear()

class Solution:

	def diagonalSort(self, matrix, n, m):
		diagonalSort1(matrix)


class Solution:

	def diagonalSort(self, matrix, n, m):
		r = 0
		k = m - 2
		c = k
		while k >= 1:
			temp = []
			while c <= m - 1 and r <= n - 1 and (r >= 0):
				temp.append(matrix[r][c])
				c += 1
				r += 1
			r = 0
			temp.sort()
			temp = temp[::-1]
			c = k
			i = 0
			while c <= m - 1 and r <= n - 1 and (r >= 0):
				matrix[r][c] = temp[i]
				c += 1
				r += 1
				i += 1
			r = 0
			k -= 1
			c = k
		r = 1
		k = 1
		c = 0
		while k <= n - 1:
			temp = []
			while r <= n - 1 and c <= m - 1 and (c >= 0):
				temp.append(matrix[r][c])
				c += 1
				r += 1
			r = k
			temp.sort()
			c = 0
			i = 0
			while r <= n - 1 and c <= m - 1 and (c >= 0):
				matrix[r][c] = temp[i]
				c += 1
				r += 1
				i += 1
			k += 1
			r = k
			c = 0
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		for i in range(1, m):
			row = 0
			col = i
			L = []
			while row < n and col < m:
				L.append(matrix[row][col])
				row += 1
				col += 1
			L.sort(reverse=True)
			row = 0
			col = i
			k = 0
			while row < n and col < m:
				matrix[row][col] = L[k]
				k += 1
				row += 1
				col += 1
		for i in range(1, n):
			row = i
			col = 0
			L = []
			while row < n and col < m:
				L.append(matrix[row][col])
				row += 1
				col += 1
			L.sort()
			k = 0
			row = i
			col = 0
			while row < n and col < m:
				matrix[row][col] = L[k]
				k += 1
				col += 1
				row += 1
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		d = {}
		for i in range(n):
			for j in range(m):
				if i - j not in d:
					d[i - j] = [matrix[i][j]]
				else:
					d[i - j].append(matrix[i][j])
		for keys in d:
			if keys > 0:
				d[keys] = sorted(d[keys])
			elif keys < 0:
				d[keys] = sorted(d[keys], reverse=True)
		for i in range(n):
			for j in range(m):
				matrix[i][j] = d[i - j].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		left = []
		right = []
		l = []
		for i in range(n):
			left.append([])
		for j in range(m):
			right.append([])
		for i in range(n):
			for j in range(m):
				if i > j:
					left[i - j].append(matrix[i][j])
				if j > i:
					right[j - i].append(matrix[i][j])
		for i in left:
			i.sort()
			i.reverse()
		for i in right:
			i.sort()
		for i in range(n):
			for j in range(m):
				if j > i:
					matrix[i][j] = right[j - i].pop()
				if i > j:
					matrix[i][j] = left[i - j].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		start_num = [(0, x) for x in range(m)] + [(y, 0) for y in range(n)]
		start_num.pop(0)
		for (x, y) in start_num:
			if x == y:
				continue
			step = min(abs(n - x - 1), abs(m - y - 1))
			line_list = [(x + i, y + i) for i in range(step + 1)]
			point_list = [matrix[i][j] for (i, j) in line_list]
			if x < y:
				point_list.sort(reverse=True)
			else:
				point_list.sort()
			for (i, j) in line_list:
				matrix[i][j] = point_list.pop(0)
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		s = defaultdict(list)
		for r in range(n):
			for c in range(m):
				if r - c == 0:
					continue
				s[r - c].append(matrix[r][c])
		for (k, li) in s.items():
			if k <= 0:
				li.sort(reverse=True)
			else:
				li.sort()
		for r in range(n):
			for c in range(m):
				if r - c == 0:
					continue
				matrix[r][c] = s[r - c].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, matrix, n, m):
		for gap in range(1, m):
			(i, j) = (0, gap)
			temp = []
			while j < m and i < n:
				temp.append(matrix[i][j])
				j += 1
				i += 1
			(i, j) = (0, gap)
			temp.sort()
			while j < m and i < n:
				matrix[i][j] = temp.pop()
				j += 1
				i += 1
		for gap in range(1, n):
			(i, j) = (gap, 0)
			temp = []
			while i < n and j < m:
				temp.append(matrix[i][j])
				i += 1
				j += 1
			(i, j) = (gap, 0)
			temp.sort(reverse=True)
			while i < n and j < m:
				matrix[i][j] = temp.pop()
				i += 1
				j += 1


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		v = []
		for row in range(n):
			i = row
			j = 0
			while i < n and j < m:
				v.append(matrix[i][j])
				i += 1
				j += 1
			if i != j:
				v.sort()
			t = 0
			i = row
			j = 0
			while i < n and j < m:
				matrix[i][j] = v[t]
				t += 1
				i += 1
				j += 1
			v = []
		for col in range(m):
			i = 0
			j = col + 1
			while i < n and j < m:
				v.append(matrix[i][j])
				i += 1
				j += 1
			if i != j:
				v.sort(reverse=True)
			t = 0
			i = 0
			j = col + 1
			while i < n and j < m:
				matrix[i][j] = v[t]
				t += 1
				i += 1
				j += 1
			v = []
		return matrix


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		to = defaultdict(list)
		for row in range(n):
			for col in range(m):
				to[row - col].append(matrix[row][col])
		for i in to:
			if i < 0:
				to[i].sort(reverse=True)
			elif i > 0:
				to[i].sort()
		for row in range(n):
			for col in range(m):
				matrix[row][col] = to[row - col].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, a, n, m):
		for p in range(1, n):
			temp1 = []
			i = p
			j = 0
			while i < n and j < m:
				temp1.append(a[i][j])
				i += 1
				j += 1
			temp1.sort()
			k = 0
			i = p
			j = 0
			while i < n and j < m:
				a[i][j] = temp1[k]
				i += 1
				j += 1
				k += 1
		for p in range(0, m):
			temp1 = []
			i = 0
			j = p + 1
			while i < n and j < m:
				temp1.append(a[i][j])
				i += 1
				j += 1
			temp1.sort(reverse=True)
			i = 0
			j = p + 1
			k = 0
			while i < n and j < m:
				a[i][j] = temp1[k]
				i += 1
				j += 1
				k += 1
		return a


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		d = defaultdict(list)
		i = 0
		while i < n:
			j = 0
			while j < m:
				d[j - i].append(matrix[i][j])
				j = j + 1
			i = i + 1
		for key in d:
			if key == 0:
				continue
			elif key > 0:
				d[key].sort(reverse=True)
			elif key < 0:
				d[key].sort()
		i = 0
		j = 0
		while i < n:
			j = 0
			while j < m:
				matrix[i][j] = d[j - i].pop(0)
				j = j + 1
			i = i + 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		hm = dict()
		for i in range(n):
			for j in range(m):
				if i - j in hm:
					hm[i - j].append(matrix[i][j])
				else:
					hm[i - j] = [matrix[i][j]]
		from collections import deque
		for i in hm:
			hm[i] = deque(sorted(hm[i]))
		for i in range(n):
			for j in range(m):
				if i - j > 0:
					matrix[i][j] = hm[i - j].popleft()
				if i - j < 0:
					matrix[i][j] = hm[i - j].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		upper = []
		for i in range(m - 1):
			upper.append([])
		lower = []
		for i in range(n - 1):
			lower.append([])
		for i in range(0, n):
			for j in range(i + 1, m):
				upper[j - i - 1].append(matrix[i][j])
		for i in range(0, n):
			for j in range(0, min(i, m)):
				lower[i - j - 1].append(matrix[i][j])
		for l in upper:
			l.sort()
		for l in lower:
			l.sort(reverse=True)
		for i in range(0, n):
			for j in range(i + 1, m):
				matrix[i][j] = upper[j - i - 1].pop()
		for i in range(0, n):
			for j in range(0, min(i, m)):
				matrix[i][j] = lower[i - j - 1].pop()


from collections import defaultdict

class Solution:

	def diagonalSort(self, matrix, n, m):
		to = defaultdict(list)
		for i in range(n):
			for j in range(m):
				to[i - j].append(matrix[i][j])
		for key in to.keys():
			to[key] = sorted(to[key])
		for i in range(n):
			for j in range(m):
				if i - j > 0:
					matrix[i][j] = to[i - j].pop(0)
				elif i - j < 0:
					matrix[i][j] = to[i - j].pop(-1)


class Solution:

	def diagonalSort(self, matrix, n, m):
		lower_tr = [[] for i in range(n)]
		upper_tr = [[] for i in range(m)]
		major = []
		for i in range(n):
			for j in range(m):
				if j < i:
					lower_tr[i - j].append(matrix[i][j])
				elif i < j:
					upper_tr[j - i].append(matrix[i][j])
				else:
					major.append(matrix[i][j])
		for i in range(n):
			lower_tr[i].sort(reverse=True)
		for j in range(m):
			upper_tr[j].sort()
		for i in range(n):
			for j in range(m):
				if j < i:
					elem = lower_tr[i - j].pop()
					matrix[i][j] = elem
				elif j > i:
					d = j - i
					l = len(upper_tr[d]) - 1
					matrix[i][j] = upper_tr[d][l]
					upper_tr[d].pop()


class Solution:

	def diagonalSort(self, mat, n, m):
		ti = 1
		tj = 0
		while ti < n:
			tmp = []
			i = ti
			j = 0
			while i < n and j < m:
				tmp.append(mat[i][j])
				i += 1
				j += 1
			tmp = sorted(tmp)
			i = ti
			j = 0
			k = 0
			while k < len(tmp):
				mat[i][j] = tmp[k]
				i += 1
				j += 1
				k += 1
			ti += 1
		ti = 1
		while ti < m:
			tmp = []
			j = ti
			i = 0
			while i < n and j < m:
				tmp.append(mat[i][j])
				i += 1
				j += 1
			tmp = sorted(tmp, reverse=True)
			i = 0
			j = ti
			k = 0
			while k < len(tmp):
				mat[i][j] = tmp[k]
				i += 1
				j += 1
				k += 1
			ti += 1
		return mat


class Solution:

	def diagonalSort(self, matrix, n, m):
		k = dict()
		for i in range(n):
			for j in range(m):
				if k.get(j - i):
					k[j - i].append(matrix[i][j])
				else:
					k[j - i] = [matrix[i][j]]
		for keys in k.keys():
			if keys != 0:
				if keys < 0:
					k[keys].sort(reverse=True)
				else:
					k[keys].sort()
		for i in range(n):
			for j in range(m):
				if i - j == 0:
					continue
				matrix[i][j] = k[j - i].pop()


class Solution:

	def diagonalSort(self, matrix, n, m):
		groups_dict = {}
		for i in range(n):
			for j in range(m):
				group = i - j
				if group in groups_dict.keys():
					groups_dict[group].append(matrix[i][j])
				else:
					groups_dict[group] = [matrix[i][j]]
		for (k, v) in groups_dict.items():
			if k < 0:
				groups_dict[k] = sorted(groups_dict[k], reverse=True)
			elif k > 0:
				groups_dict[k] = sorted(groups_dict[k])
		for i in range(n):
			for j in range(m):
				matrix[i][j] = groups_dict[i - j].pop(0)
		return matrix


class Solution:

	def diagonalSort(self, mat, n, m):
		if n == 1 or m == 1:
			return mat
		diff = 1
		while diff < n - 1:
			i = diff
			j = 0
			temp = []
			while i < n and j < m:
				temp.append(mat[i][j])
				j += 1
				i += 1
			temp.sort()
			i = diff
			j = 0
			index = 0
			while i < n and j < m:
				mat[i][j] = temp[index]
				index += 1
				i += 1
				j += 1
			diff += 1
		diff = 1
		while diff < m - 1:
			j = diff
			i = 0
			temp = []
			while j < m and i < n:
				temp.append(mat[i][j])
				j += 1
				i += 1
			temp.sort(reverse=True)
			j = diff
			i = 0
			index = 0
			while j < m and i < n:
				mat[i][j] = temp[index]
				index += 1
				i += 1
				j += 1
			diff += 1
		return mat


class Solution:

	def diagonalSort(self, matrix, n, m):
		arr = []
		for first in range(1, m):
			j = first
			i = 0
			arr.clear()
			while i < n and j < m:
				arr.append(matrix[i][j])
				i += 1
				j += 1
			arr.sort(reverse=True)
			j = first
			i = 0
			k = 0
			while k < len(arr):
				matrix[i][j] = arr[k]
				i += 1
				j += 1
				k += 1
		for first in range(1, n):
			i = first
			j = 0
			arr.clear()
			while i < n and j < m:
				arr.append(matrix[i][j])
				i += 1
				j += 1
			arr.sort()
			i = first
			j = 0
			k = 0
			while k < len(arr):
				matrix[i][j] = arr[k]
				i += 1
				j += 1
				k += 1


class Solution:

	def diagonalSort(self, matrix, n, m):
		mp = {}
		for i in range(n):
			for j in range(m):
				if i != j:
					if i - j in mp:
						mp[i - j].append(matrix[i][j])
					else:
						mp[i - j] = [matrix[i][j]]
		for i in mp:
			if i > 0:
				mp[i].sort(reverse=True)
			else:
				mp[i].sort()
		for i in range(n):
			for j in range(m):
				if i != j:
					matrix[i][j] = mp[i - j].pop()
		return matrix