For crater exploration purposes, the Arecibo telescope records images of Saturn’s
satellites. The scientific team must distinguish between satellite images and group
the images by satellite, but it’s not that simple because satellites could be shot
from different angles.
Captured images can be displayed as \(n \times m\) matrices, filled with ’*’ (crater) and
’.’ (plain surface). We say that two images correspond to the same satellite if one can get the other by
circular shifts of rows and columns.
To make the verification process easier, scientists want to find the lexicographically smallest image
corresponding to the satellite from the given image. When comparing images, we compare strings obtained
by concatenating all rows of the image, where characters are compared by ASCII value.

Subtask 1 (10 points): \(1 \le n\), \(m \le 50\)

Subtask 2 (40 points): \(1 \le n\), \(m \le 300\)

Subtask 3 (60 points): No additional constraints.

The first line contains integers \(n\) and \(m\) (\(1 \le n\), \(m \le 1000\)), the dimensions of the image.
Each of the following \(n\) lines contains \(m\) characters ’*’ and ’.’. This represents the captured image.

Output \(n\) lines with \(m\) characters each, the wanted lexicographically smallest image.

생성자가 기록되지 않았습니다.

출처 COCI 2020/2021 Contest 3