Pacman is cleaning his ice rink! The rink, like everything in PacMan’s universe, wraps! In other words, if you go off the edge of the rectangular rink to the right, you’ll end up in the same row on the left side of the rink. Go off of the left side of the rink, and you’ll end up on the right. Going up off the top of the rink causes you to end up in the same column but on the bottom. Go off of the bottom, and you’ll end up at the top.

What makes this zamboni special is that when it cleans the ice, it leaves a color on the ice! At the start, the ice is colorless (white). Whenever the zamboni is on a cell of ice, it overwrites the color on that cell. Each color is represented by a capital letter of the alphabet. The colors are in alphabetical order. The zamboni switches to the next letter in the alphabet at each step, and wraps at the end of the alphabet. If the current color is P, the next color is Q. If the current color is Z, the next color is A.

PacMan uses a very specific algorithm to clean the ice:

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 is originally facing up. Knowing where the zamboni starts, the size of the rink, and the number of steps taken, determine what the ice looks like after the zamboni has completed its run.

-----Input-----
Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each input consists of a single line with $5$ space-separated integers, $r\ c\ i\ j\ n$, where:
 - $r$ ($1 \le r \le 2000$) is the number of rows of the ice rink
 - $c$ ($1 \le c \le 2000$) is the number of columns of the ice 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 (numSteps in PacMan’s algorithm)

Note that row $1$ is the top row, and column $1$ is the left column.

-----Output-----
Output the state of the ice rink after the zamboni has completed its run, as a $r \times c$ grid of characters. Each character should be a capital letter (A-Z) representing the color of the ice, or a dot (.) if the ice is white, or an ’at’ sign (@) if the cell is the final location of the Zamboni.

-----Examples-----
Sample Input:
5 5 3 3 4
Sample Output:
.....
..BBC
..A.C
....C
@DDDD

Source: kattis | Difficulty: HARD


Solutions: