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.


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.


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


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


3 3
1 2 3
8 9 4
7 6 5
1 2 3 4 5 6 7 8 9

Sponsors Gold