A circuit-board tester reads an R-by-C grid of integer probe values along its anti-diagonals (an anti-diagonal is the set of cells whose row index plus column index is constant), alternating direction to make one continuous zigzag sweep.
The sweep works as follows. Process anti-diagonals in order of increasing index d = 0, 1, ..., R+C-2. For an even d, emit that anti-diagonal's cells going upward (from the largest row index up to the smallest). For an odd d, emit that anti-diagonal's cells going downward (from the smallest row index down to the largest). Concatenate all anti-diagonals in this order.
For the grid [[1,2,3],[4,5,6],[7,8,9]] the readout is 1 2 4 7 5 3 6 8 9.
Input format
Line 1: two integers R and C.
Next R lines: each contains C space-separated integers (one grid row).
Output format
A single line: all R*C values in zigzag anti-diagonal order, space-separated.
Constraints
- 1 <= R, C <= 200
- -1000000000 <= each value <= 1000000000