Diagonal Traversal of a Matrix

You are given a matrix A with N rows and M columns. Your task is to traverse the matrix in a diagonal order starting from the top-left corner and moving towards the bottom-right corner.

The traversal is defined as follows:

First, for each column j in the first row (i.e. when i = 0), traverse diagonally downwards: starting at (0, j), move to (1, j-1), then (2, j-2), and so on until you exit the matrix boundaries. Secondly, for each row i starting from the second row (i ≥ 1) in the last column, traverse similarly: starting at (i, M-1), then (i+1, M-2), etc.

Mathematically, if we denote the matrix index by \( (i, j) \), then the diagonal traversal can be described by the following process:

1. For each \( j = 0, 1, \dots, M-1 \), process the diagonal starting at \( (0, j) \): \[ \text{while } i < N \text{ and } j \ge 0, \text{ output } A[i][j], \text{ then do } i \leftarrow i+1,\; j \leftarrow j-1. \]
2. For each \( i = 1, 2, \dots, N-1 \), process the diagonal starting at \( (i, M-1) \): \[ \text{while } i < N \text{ and } j \ge 0, \text{ output } A[i][j], \text{ then do } i \leftarrow i+1,\; j \leftarrow j-1. \]

Print the resulting sequence of numbers separated by a single space.

inputFormat

The first line of input contains two space-separated integers N and M, representing the number of rows and columns in the matrix, respectively. This is followed by N lines, each containing M space-separated integers representing the elements of the matrix A.

For example:

2 3
1 2 3
4 5 6

outputFormat

Output a single line containing the elements of the matrix in diagonal order separated by a single space.

For the sample input above, the output should be:

1 2 4 3 5 6

## sample

2 3
1 2 3
4 5 6

1 2 4 3 5 6