뱀

$N \times N$ 크기의 격자판 위를 뱀 몇 마리가 기어간다. 각 뱀은 두 칸 이상으로 이루어진 칸의 열을 차지하고, 열에서 연속한 두 칸은 변을 맞대고 있다. 열의 첫 칸을 머리라고 한다. 한 칸에는 뱀이 최대 한 마리만 있다. 처음에 뱀이 차지하지 않은 칸은 빈 칸이거나 장애물이 놓인 칸이다.

뱀은 한 걸음마다 먼저 머리를 인접한 빈 칸으로 옮기고, 그다음 꼬리를 당겨 한 칸을 비운다. 처음 진행 방향은 머리와 열에서 두 번째 칸의 위치 관계로 정해진다. 각 걸음에서 뱀은 다음 규칙을 따른다.

• 앞으로 갈 수 있으면, 즉 장애물이나 다른 뱀이나 자기 몸에 부딪히지 않고 판을 벗어나지도 않으면 앞으로 간다.
• 앞으로 갈 수 없으면 오른쪽으로 꺾으려 한다.
• 그것도 불가능하면 왼쪽으로 꺾으려 한다.
• 그것도 불가능하면 제자리에 머무르고, 다음 걸음에서 다시 앞으로 가려 한다.

오른쪽과 왼쪽은 뱀이 지금 향한 방향을 기준으로 정한다. 꺾어서 움직이면 그 방향이 새로운 진행 방향이 되고, 제자리에 머무르면 방향은 그대로다.

머리가 옮겨 갈 칸은 판단하는 그 순간에 비어 있어야 한다. 꼬리는 머리를 옮긴 뒤에 당기므로 꼬리 끝이 있는 칸은 아직 비어 있지 않고, 따라서 머리는 자기 꼬리 끝 칸으로 들어가지 못한다.

판 위의 뱀은 영어 알파벳으로 구분한다. 한 걸음마다 모든 뱀이 알파벳 순서로 차례차례 위 규칙에 따라 움직인다. 같은 걸음에서 먼저 움직인 뱀이 비운 칸은 나중에 움직이는 뱀이 쓸 수 있다. 한 걸음은 정확히 1초가 걸린다. 뱀의 처음 배치가 주어질 때 $T$초가 지난 뒤의 배치를 구하는 프로그램을 작성하라.

첫 줄에 정수 $N$과 $T$가 주어진다. $2 \le N \le 1000$, $1 \le T \le 10^6$이다. $N$은 판의 한 변의 길이이고, $T$는 뱀의 배치를 구할 시각이다.

다음 $N$개 줄에는 각각 $N$개의 문자가 주어진다. 이 줄은 뱀과 빈 칸과 장애물의 처음 배치를 나타내며, 각 문자는 다음 중 하나다.

• . : 빈 칸
• # : 장애물이 있는 칸
• 영어 대문자 : 뱀의 머리가 있는 칸
• 영어 소문자 : 뱀의 머리가 아닌 부분이 있는 칸

같은 알파벳이 적힌 칸은 대소문자를 가리지 않고 모두 한 뱀을 이룬다. 한 뱀을 이루는 각 칸은 그 뱀의 다른 칸과 정확히 두 칸 인접하고, 머리와 꼬리 끝만 정확히 한 칸과 인접한다. 같은 알파벳으로 표시된 서로 다른 뱀은 없다.

$N$개 줄에 각각 $N$개의 문자를 출력한다. 이 줄은 $T$초가 지난 뒤의 배치를 입력과 같은 형식으로 나타내야 한다.