#107Medium

Spiral order

Time: 1 s · Memory: 256 MB

Matrices

Statement

Print the elements of an $m \times n$ matrix in a clockwise spiral: from the top-left corner, row 1 left to right, the last column top to bottom, the last row right to left, column 1 bottom to top, then the inner ring, and so on. Every element is printed exactly once.

Input format

The first line contains $m$ and $n$ ( $1 \le m, n \le 100$ ). Each of the next $m$ lines contains $n$ integers ( $|a_{ij}| \le 10^9$ ).

Output format

A single line with $m \cdot n$ numbers.

Examples

Input

Output

1 2 3 6 9 8 7 4 5

Input

2 4
1 2 3 4
5 6 7 8

Output

1 2 3 4 8 7 6 5

Note

Keep four borders: top, bottom, left and right. After walking a side, move the matching border one step inwards. When a single row or column is left, re-check the borders so it is not printed twice. In the second example: 1 2 3 4 8 7 6 5.

Spiral order

Time: 1 s · Memory: 256 MB

Matrices

Statement

Input format

The first line contains $m$ and $n$ ( $1 \le m, n \le 100$ ). Each of the next $m$ lines contains $n$ integers ( $|a_{ij}| \le 10^9$ ).

Output format

A single line with $m \cdot n$ numbers.

Examples

Input

Output

1 2 3 6 9 8 7 4 5

Input

2 4
1 2 3 4
5 6 7 8

Output

1 2 3 4 8 7 6 5