Rainbow Zamboni

PacMan is cleaning his ice rink. The rink wraps around, the way everything else in PacMan's universe does. Go off the right edge of the rectangular rink and you come back on the left edge in the same row. Go off the left edge and you come back on the right. Going off the top edge puts you at the bottom of the same column, and going off the bottom edge puts you at the top.

The zamboni leaves color on the ice while it cleans. At the start the ice is colorless (white). The cell the zamboni sits on takes the current color of the zamboni. Colors are capital letters and change in alphabetical order, wrapping from Z back to A. If the current color is P, the next color is Q. The color at the start is A.

PacMan cleans the ice with this algorithm.

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

The zamboni moves one cell at a time and paints every cell it passes over with the current color. The cell it stands on always carries the current color as well, so switching colors repaints that cell. The zamboni starts out facing up. You are given the starting cell, the size of the rink and the number of steps. Determine what the ice looks like after the zamboni finishes its run.

The input is a single line with five space separated integers $r$, $c$, $i$, $j$, $n$.

• $r$ ($1 \le r \le 2000$) is the number of rows of the rink
• $c$ ($1 \le c \le 2000$) is the number of columns of the rink
• $i$ ($1 \le i \le r$) is the starting row of the zamboni
• $j$ ($1 \le j \le c$) is the starting column of the zamboni
• $n$ ($1 \le n \le 10^{18}$) is the number of steps, the value numSteps in the algorithm

Row 1 is the top row and column 1 is the left column.

Print the state of the ice after the zamboni has finished, as a grid of $r \times c$ characters. Print a capital letter for a colored cell, a dot (.) for a cell that is still white, and an at sign (@) for the cell where the zamboni ends.