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

**lines of input contain**

`N`**space-separated values, representing the original matrix.**

`M`### 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

Input | Output |
---|---|

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

# C++ (Inelus Gabriel)

1 #include <cstdio> 2 int N, M, A[1005][1005]; 3 int main() 4 { 5 scanf("%d%d", &N, &M); 6 for(int i = 1; i <= N; ++i) 7 { 8 A[i][0] = A[i][M+1] = -1; 9 for(int j = 1; j <= M; ++j) 10 scanf("%d",&A[i][j]); 11 } 12 13 for(int j = 1; j <= M; ++j) 14 A[0][j] = A[N+1][j] = -1; 15 16 int i = 1, j = 1, ok = 1; 17 printf("%d ",A[i][j]); A[i][j] = -1; 18 while(ok) { 19 ok = 0; 20 while(A[i][j+1] != -1) { ok = 1; ++j; printf("%d ", A[i][j]); A[i][j] = -1; } 21 while(A[i+1][j] != -1) { ok = 1; ++i; printf("%d ", A[i][j]); A[i][j] = -1; } 22 while(A[i][j-1] != -1) { ok = 1; --j; printf("%d ", A[i][j]); A[i][j] = -1; } 23 while(A[i-1][j] != -1) { ok = 1; --i; printf("%d ", A[i][j]); A[i][j] = -1; } 24 } 25 return 0; 26 }

# Python 2.7 (Sergiu Puscas)

1 n, m = map(int, raw_input().split()) 2 a = [list(raw_input().split()) for i in range(n)] 3 4 U, D, L, R = 0, n-1, 0, m-1 5 direction = 0 6 i, j = 0, 0 7 8 for step in range(n*m): 9 print a[i][j], 10 11 if direction == 0: # right 12 if j+1 > R: # change to down 13 direction = 1 14 R -= 1 15 i += 1 16 else: 17 j += 1 18 19 elif direction == 1: # down 20 if i+1 > D: # change to left 21 direction = 2 22 D -= 1 23 j -= 1 24 else: 25 i += 1 26 27 elif direction == 2: # left 28 if j - 1 < L: # change to up 29 direction = 3 30 L += 1 31 i -= 1 32 else: 33 j -= 1 34 35 elif direction == 3: # up 36 if i - 1 <= U: # change to right 37 direction = 0 38 U += 1 39 j += 1 40 else: 41 i -= 1