为了探测陨石坑，阿雷西博望远镜拍摄了土星卫星的图像。科学团队必须区分这些卫星图像并按卫星进行分组，但这并不简单，因为卫星可能是从不同的角度拍摄的。
拍摄到的图像可以表示为一个 $n \times m$ 的矩阵，其中充满字符 *（代表陨石坑）和 .（代表平坦表面）。如果可以通过对行和列进行循环移位将一张图像变换为另一张图像，则称这两张图像对应于同一颗卫星。
为了简化验证过程，科学家们希望从给定的图像中找到对应于该卫星的字典序最小的图像。在比较图像时，我们比较将图像的所有行按顺序拼接得到的字符串，字符按 ASCII 值进行比较。
输入格式
第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），表示图像的尺寸。
接下来的 $n$ 行，每行包含 $m$ 个字符 * 和 .，表示拍摄到的图像。
输出格式
输出 $n$ 行，每行包含 $m$ 个字符，表示所求的字典序最小的图像。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 10 | $1 \le n, m \le 50$ |
| 2 | 40 | $1 \le n, m \le 300$ |
| 3 | 60 | 无附加限制。 |
样例
输入样例 1
3 3 .** *.. .*.
输出样例 1
**. ..* *..
输入样例 2
3 4 .... ..*. ....
输出样例 2
*... .... ....
输入样例 3
3 5 .**.. .***. ..**.
输出样例 3
***.. .**.. **...
说明
第一个样例的解释：
所有可以通过循环移位得到的图像为：
.** .*. *.. **. *.. ..* *.* ..* .*. *.. .** .*. ..* **. *.. .*. *.* ..* .*. *.. .** *.. ..* **. ..* .*. *.*