Giải mật thư

Trong một trò chơi TeamBuilding, nhóm của bạn nhận được một bức mật thư là một bảng số kích thước \(M \times N\), mỗi ô chứa một số nguyên.

Bảng phân đoạn cho biết để giải mật thư, ta cần sắp xếp lại tất cả các số trong bảng theo thứ tự không giảm, sau đó điền chúng vào bảng theo thứ tự các ô trên một đường xoắn ốc theo chiều kim đồng hồ bắt đầu từ ô góc trên bên trái (đi sang phải, xuống, sang trái, lên, ...).

Hãy lập trình tạo ra bảng sau khi sắp xếp và điền theo đường xoắn ốc như mô tả.

Input

Dữ liệu vào từ tệp CAU2.INP:

• Dòng \(1\): Hai số nguyên dương \(M, N\) \((M, N \le 1000)\).
• \(M\) dòng tiếp theo: mỗi dòng chứa \(N\) số nguyên \(a_{i,j}\) \((0 \le a_{i,j} \le 1000)\).

Output

Ghi ra tệp CAU2.OUT gồm \(M\) dòng, mỗi dòng chứa \(N\) số nguyên mô tả bảng kết quả (các số trên cùng một dòng cách nhau bởi đúng một dấu cách).

Input

%
4 5
2 5 1 7 9
1 1 2 2 5
0 3 3 1 8
4 1 1 4 2

Output

%
0 1 1 1 1
4 4 5 5 1
3 9 8 7 1
3 2 2 2 2

Scoring

• (30%) \(M, N \le 10\).
• (40%) \(M, N \le 100\).
• (30%) \(M, N \le 1000\).