from typing import *


class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        m, n = len(matrix), len(matrix[0])
        rtn = []
        for k in range(0, m + n - 1):
            if k % 2 == 0:
                i, j = min(k, m-1), k - min(k, m-1)
                while 0 <= i <= m-1 and 0 <= j <= n-1:
                    rtn.append(matrix[i][j])
                    i, j = i - 1, j + 1
            else:
                i, j = k - min(k, n-1), min(k, n-1)
                while 0 <= i <= m-1 and 0 <= j <= n-1:
                    rtn.append(matrix[i][j])
                    i, j = i + 1, j - 1
        return rtn


if __name__=='__main__':
    s = Solution()
    print(s.findDiagonalOrder([[1,2,3],[4,5,6],[7,8,9],[11,12,13]]))
