Diagonal Sort

Given a two-dimensional integer matrix, sort each of the diagonals descending from left to right in ascending order.

Constraints

• n, m ≤ 25 where n and m are the rows and columns of matrix

https://binarysearch.com/problems/Diagonal-Sort

Examples

Example 1

Input

• matrix =

[[9,8,7],
 [6,5,4],
 [3,2,1]]

Output

• answer = [[1, 4, 7], [2, 5, 8], [3, 6, 9]]

Solution