테라리움

동물학 연구소에 희귀한 뱀들을 키우는 테라리움이 있다. 테라리움은 흙으로 채워진 납작한 상자이며, 윗면이 유리로 되어 있어 뱀을 위에서 관찰할 수 있다. 흙에는 도랑이 파여 있고, 뱀들은 이 도랑을 따라 끊임없이 이동한다. 모든 뱀의 지름은 $1$ cm이고, 길이는 $2$ cm 이상의 정수이다.

연구원들은 뱀의 이동 규칙을 발견했다. 매 초마다 뱀은 머리가 향한 방향으로 앞으로 $1$ cm 이동하려고 한다. 바로 앞 칸이 장애물(벽 또는 뱀)이면, 뱀은 먼저 오른쪽으로 돌려고 한다. 오른쪽 칸도 막혀 있으면 왼쪽으로 돌려고 하고, 왼쪽 칸마저 막혀 있으면 그 초에는 제자리에서 기다린다. 여기서 오른쪽과 왼쪽은 뱀이 향한 방향을 기준으로 한 뱀 자신의 관점이다. 한 번 이동(직진이든 회전이든)하면 머리가 한 칸 나아가고, 모든 몸통 마디가 자기 자취를 따라 한 칸씩 앞으로 당겨지므로 꼬리는 원래 있던 칸을 비운다.

테라리움은 $N \times N$개의 문자로 이루어진 격자로 표현된다. 각 칸은 다음 중 하나이다.

• . — 도랑(빈 칸, 지나갈 수 있음)
• # — 벽
• A~Z — 뱀의 머리
• a~z — 뱀의 몸통 마디 또는 꼬리 끝

각 뱀은 하나의 라틴 문자로 구분된다(따라서 뱀은 최대 $26$마리이다). 머리는 대문자, 몸통은 같은 알파벳의 소문자로 나타낸다. 뱀이 향한 방향은 첫 번째 몸통 마디에서 머리를 향하는 방향이다.

매 초마다 뱀들은 알파벳 순서대로 한 마리씩(A, 그다음 B, …) 이동을 시도한다. 각 뱀은 같은 초에 이미 이동한 뱀들이 남긴 격자 상태를 보고 행동한다. $T$초가 지난 뒤 테라리움의 상태를 출력하라.

첫 줄에 두 정수 $N$과 $T$가 주어진다. 이어지는 $N$개의 줄에는 각각 $N$개의 문자가 주어지며, 테라리움의 초기 상태를 나타낸다.

입력은 뱀을 항상 명확하게 구분할 수 있도록 보장된다. 모든 뱀은 하나로 이어진 사슬이며, 몸통 중간의 각 마디는 같은 뱀에 속한 이웃이 정확히 둘, 머리와 꼬리 끝은 그런 이웃이 정확히 하나이다.

$T$초가 지난 뒤 테라리움의 상태를, 입력과 같은 문자 규칙으로 $N$줄, 각 줄 $N$문자로 출력한다.

• $2 \le N \le 1000$
• $1 \le T \le 10^6$