COCI 2020/2021 - Contest 3 - Sateliti

View as PDF

Submit solution

Points: 1.30 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Suggester:
Problem source:
COCI 2020/2021 - Contest 3
Problem types
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Với mục đích thăm dò núi lửa, kính thiên văn Arecibo được dùng để chụp ảnh của các vệ tinh tự nhiên của Sao Thổ. Các nhà khoa học phải phân biệt giữa các tấm ảnh vệ tinh và nhóm các tấm ảnh ấy theo từng vệ tinh. Đây là một việc không hề đơn giản do các vệ tinh có thể được chụp từ nhiều góc nhìn khác nhau.

Mỗi tấm ảnh có thể được thể hiện dưới dạng một ma trận ~n×m~, được lấp đầy bởi * (núi lửa) và . (đất trống). Hai tấm ảnh có thể được xem là của cùng một vệ tính nếu như từ một tấm ảnh có thể chuyển thành tấm ảnh còn lại bằng các phép dịch chuyển vòng tròn giữa các hàng và các cột.

Để giúp quá trình xác minh dễ dàng hơn, các nhà khoa học muốn tìm tấm ảnh với thứ tự từ điển nhỏ nhất của cùng vệ tinh từ tấm ảnh đã cho. Khi so sánh thứ tự từ điển giữa hai tấm ảnh, chúng ta so sánh thứ tự từ điển giữa hai chuỗi thu được bằng cách nối tất cả các hàng của tấm ảnh, trong đó mỗi ký tự được so sánh với nhau bằng giá trị ASCII.

Input

Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~ ~(1 \leq n,m \leq 1000)~, kích thước của tấm ảnh.

Mỗi dòng trong số ~n~ dòng tiếp theo chứa ~m~ kí tự *., thể hiện tấm ảnh được chụp.

Output

In ra ~n~ dòng, mỗi dòng gồm ~m~ kí tự, thể hiện tấm ảnh với thứ tự từ điển nhỏ nhất từ tấm ảnh đã cho.

Subtask

  • ~7~ test có ~1 \leq n,m \leq 50~
  • ~10~ test khác có ~1 \leq n, m \leq 300~
  • ~10~ test còn lại không có ràng buộc gì thêm.

Sample 1

Input
3 3
.**
*..
.*.
Output
**.
..*
*..
Giải thích

Dưới đây là tất cả mọi tấm ảnh có thể chuyển từ tấm ảnh đã cho bằng các phép dịch chuyển vòng tròn giữa các hàng và các cột:

.**     .*.     *..     **.     *..     ..*     *.*     ..*     .*. 
*..     .**     .*.     ..*     **.     *..     .*.     *.*     ..*
.*.     *..     .**     *..     ..*     **.     ..*     .*.     *.*

Sample 2

Input
3 4
....
..*.
....
Output
*...
....
....

Sample 3

Input
3 5
.**..
.***.
..**.
Output
***..
.**..
**...

Comments

Please read the guidelines before commenting.


There are no comments at the moment.