Cho một bảng ~m~ dòng ~n~ cột. Trên mỗi ô của bảng có một ký tự * hoặc ..

Ta định nghĩa phép so sánh hai bảng ~m \times n~ là so sánh hai xâu ký tự có được bằng cách ghép liên tiếp các hàng của bảng.

Xét các phép biến đổi bảng bằng cách dịch chuyển theo vòng tròn các hàng hoặc các cột. Hãy biến đổi bảng đã cho thành bảng có thứ tự từ điển nhỏ nhất.

Yêu cầu: Hãy biến đổi bảng đã cho thành bảng có thứ tự từ điển nhỏ nhất và in ra bảng đó.

Input

• Dòng đầu chứa hai số nguyên dương ~m, n~ (~1 \le m, n \le 1000~);
• ~m~ dòng tiếp theo, mỗi dòng chứa một xâu ký tự độ dài ~n~ chỉ gồm các ký tự * và . mô tả một hàng của bảng.

Output

• Ghi ra ~m~ dòng, mỗi dòng ~n~ ký tự mô tả bảng nhỏ nhất biến đổi được.