Spiral

Little Spiderman has forgotten that he has another homework. He has a matrix and he wants to write the elements spirally clock-wise, from the outside to the inside. He starts from the top-left corner, advances to the right until he reaches the top-right corner, then down until bottom-right corner, then left to the bottom-left corner, then up again. Before reaching an already written element, he always makes a right turn. Read the sample for clarification.

Input

The first line of input contains integers N and M.
The next N lines of input contain M space-separated values, representing the original matrix.

Output

The first line of output should contain M x N values, separated by spaces, representing the matrix elements written spirally clock-wise.

Constraints

  • 1 ≤ N, M ≤ 1000
  • 1 ≤ any matrix value ≤ 32768

Sample

InputOutput
3 3
1 2 3
8 9 4
7 6 5
1 2 3 4 5 6 7 8 9
Questions?

Sponsors Gold