정올국의 우주 행성 탐사선 KOI호가 마침내 목표로 한 외계 행성에 도달했다.

외계 행성 탐사의 목적은 인류의 이주이기 때문에, 무엇보다도 물로 이루어진 바다의 존재가 가장 중요하다.

KOI호는 행성 주위를 공전하며 행성 전체를 N행 M열의 픽셀 사진으로 변환하는데 성공했다.

각 픽셀에는 물을 뜻하는 '*' 혹은 땅을 뜻하는 '.'이 저장되어 있다.

사전순으로 '*'가 '.' 앞에 온다는 사실을 유념하자.

지구에 남아있는 과학자들은 자신들의 발견을 강조하기 위해 이 픽셀 사진을 약간 수정하려고 한다.

픽셀 전체를 가로 혹은 세로 방향, 혹은 두 가지 방법을 섞어서 원형 이동하는 방법으로

픽셀 전체가 사전순으로 가장 작아지도록 하기를 원한다.

픽셀 사진의 정보를 NM 크기의 이차원 배열 A에 저장했다고 가정하자.

오른쪽으로 한칸 원형 이동시키는 것은, A[i][j]의 값을 A[i][(j+1)%M]에 담는 것과 같고, 다른 방향도 비슷하게 정의된다.

또, 두 개의 픽셀 사진을 사전순으로 비교한 결과는 첫 번째 행 뒤에 두 번째 행을 붙이고,

그 뒤에 세 번째 행을 붙이고, ..., 그 뒤에 N 번째 행을 붙인 길이 NM의 문자열을 비교한 결과와 같다.

원형 이동을 적당한 횟수와 방법으로 실행하였을 때, 사전순으로 가능한 한 작은 픽셀 사진의 최종 형태를 출력하여라.

외계 행성 탐사 timer 3s memory 1024MB

외계 행성 탐사 3s 1024MB