473. Snake Loves Diagonal Move

0

Medium

Given an m x n matrix, there is a snake that loves diagonal movement. Print all the elements of the matrix starting from (0,0) and traversing in an alternating diagonal order until (m-1,n-1).

Input Format

The first line contains two space-separated integers N (number of rows) and M (number of columns).
The next N lines consist of space-separated elements of each row in the matrix.

Output Format

Print all elements of the matrix in an alternating diagonal order.

Example

Input

3 3
1 2 3
4 5 6
7 8 9

Output

1 2 4 7 5 3 6 8 9

Constraints

1 <= N, M <= 10^3
-10^4 <= matrix[i][j] <= 10^4

Loading...

View Submissions

Console