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ố có kích thước \(M \times N\), trên mỗi ô của bảng số chứa một số nguyên. Cùng với bức mật thư đó bạn cũng nhận được một nét vẽ hình xoắn ốc theo chiều kim đồng hồ. Bằng phán đoán của mình, bạn cùng nhóm của mình biết rằng để đọc được mật thư đó thì phải sắp xếp lại các ô số trong đó theo thứ tự tăng dần và theo chiều hình xoắn ốc như trong hình vẽ. Nhiệm vụ của bạn là lập trình thực hiện giải bức mật thư để giúp cả nhóm giành chiến thắng.

Input

• Dòng 1: Chứa hai số nguyên dương \(M\) và \(N\) (\(M, N \le 1000\)).
• Trong \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên dương không lớn hơn \(1000\).

Output

• Gồm \(M\) dòng, trên mỗi dòng chứa \(N\) số nguyên thể hiện bảng số kết quả giải bức mật thư (các số liền nhau trên cùng dòng được đặt cách nhau một dấu cách).

Example

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

0 1 1 1 2
5 6 7 8 2
5 12 11 9 2
4 4 3 3 3

Scoring

• Có \(30\%\) số test tương ứng với \(M, N \le 10\).
• Có \(40\%\) số test tương ứng với \(M, N \le 100\).
• Có \(30\%\) số test tương ứng với \(M, N \le 1000\).