무지개 정빙기

팩맨이 자기 아이스링크를 청소한다. 팩맨 세계의 다른 모든 것이 그렇듯 이 링크도 양쪽 끝이 이어져 있다. 직사각형 링크의 오른쪽 끝을 넘어가면 같은 행의 왼쪽 끝으로 나오고, 왼쪽 끝을 넘어가면 오른쪽 끝으로 나온다. 위쪽 끝을 넘어가면 같은 열의 아래쪽 끝으로 나오고, 아래쪽 끝을 넘어가면 위쪽 끝으로 나온다.

이 정빙기는 얼음을 닦으면서 색을 남긴다. 처음에 얼음은 색이 없는 흰색이다. 정빙기가 올라가 있는 칸은 정빙기의 현재 색으로 덮인다. 색은 알파벳 대문자로 나타내고 알파벳 순서대로 바뀌며, Z 다음에는 다시 A가 된다. 현재 색이 P면 다음 색은 Q이다. 출발할 때의 색은 A이다.

팩맨은 다음 알고리즘대로 얼음을 청소한다.

stepSize ← 1
loop numSteps times
    Move stepSize steps in the current direction
    Rotate the direction of the zamboni 90 degrees clockwise
    Switch to the next color
    stepSize ← stepSize + 1
end loop

정빙기는 한 칸씩 움직이고 지나간 칸을 모두 현재 색으로 칠한다. 서 있는 칸도 늘 현재 색이므로, 색을 바꾸면 그 자리를 새 색으로 다시 칠한다. 정빙기는 처음에 위쪽을 보고 있다. 정빙기가 출발하는 칸과 링크의 크기, 이동 횟수가 주어진다. 정빙기가 청소를 마친 뒤 얼음이 어떤 모습인지 구하시오.

입력은 한 줄이고, 공백으로 구분된 정수 다섯 개 $r$, $c$, $i$, $j$, $n$이 주어진다.

• $r$ ($1 \le r \le 2000$)은 링크의 행 개수
• $c$ ($1 \le c \le 2000$)는 링크의 열 개수
• $i$ ($1 \le i \le r$)는 정빙기가 출발하는 행
• $j$ ($1 \le j \le c$)는 정빙기가 출발하는 열
• $n$ ($1 \le n \le 10^{18}$)은 이동 횟수, 즉 알고리즘의 numSteps

행 번호 1이 맨 위 행이고, 열 번호 1이 맨 왼쪽 열이다.

정빙기가 청소를 마친 뒤 얼음의 상태를 $r \times c$ 크기의 문자 격자로 출력한다. 색이 칠해진 칸은 그 색을 나타내는 알파벳 대문자, 아직 흰색인 칸은 마침표(.), 정빙기가 마지막으로 멈춘 칸은 골뱅이표(@)로 출력한다.