Spiral Traversal

Given a 2D matrix of numbers, return a spiral traversal of the matrix in the clockwise direction.

Example

Input

matrix = [
  [1, 2, 3, 4],
  [12, 13, 14, 5],
  [11, 16, 15, 6],
  [10, 9, 8, 7],
];

Output

[
    1,  2,  3,  4,  
    5,  6, 7,  8,  
    9, 10, 11, 12,
    13, 14, 15, 16
]

Explanation

In the clockwise direction, we go from

1. Left to right (covering 1, 2, 3, 4)
2. Top to bottom (covering 5, 6, 7).
3. Right to left (covering 8, 9, 10).
4. Bottom to top (covering 11, 12). And the cycle repeats until all the numbers are covered.

Constraints

1 <= matrix.length <= 1000
1 <= matrix[i][j] <= 1000