#208MediumMatrix Traversal· Zigzag Anti-Diagonal Traversal

Diagonal Snake Order

A warehouse robot scans a rectangular shelf grid and reports the label on each shelf. To keep its arm movement smooth, it follows a **diagonal snake**: it visits the shelves along anti-diagonals (all cells with the same `row + column`), going from the diagonal that contains the top-left cell to the one that contains the bottom-right cell, and it reverses direction on every diagonal. The first diagonal is just the top-left cell. The next one is read from top to bottom (moving down and to the left), the one after that from bottom to top (moving up and to the right), and so on, alternating. Return the labels in the order the robot reads them.

Input format

`grid`: a non-empty rectangular matrix of integers.

Output format

An array with all `rows * cols` labels in snake order.

Examples

Input: grid = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

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

Diagonal sums 0 to 4 give: [1], then [2, 4] (down-left), then [7, 5, 3] (up-right), then [6, 8] (down-left), then [9].

Input: grid = [[1, 2], [3, 4]]

Output: [1, 2, 3, 4]

The diagonals are [1], [2, 3] and [4], so the order is 1, 2, 3, 4.

Input: grid = [[5], [6], [7]]

Output: [5, 6, 7]

A single column has one cell per diagonal, so the order is simply top to bottom.

Constraints

1 <= rows, cols <= 300
-1000 <= grid[r][c] <= 1000

#matrix
#traversal
#simulation
#diagonals