Jungle Robot Exploration

A robot is sent to explore a jungle whose map is given as an $n\times m$ grid. Each cell in the grid is either an obstacle or free space. An obstacle cell is represented by the character x and a free space by .. The cell in the i-th row and j-th column is denoted by $(i,j)$ where $1\le i\le n$, $1\le j\le m$.

The robot has a state determined by its position $(x,y)$ and its facing direction $d$. The direction is given by an integer $d \in \{0,1,2,3\}$ where:

• $d=0$: facing east (i.e. moving to $(x, y+1)$),
• $d=1$: facing south (i.e. moving to $(x+1, y)$),
• $d=2$: facing west (i.e. moving to $(x, y-1)$),
• $d=3$: facing north (i.e. moving to $(x-1, y)$).

The robot starts at position $(x_0,y_0)$ with initial direction $d_0$. It is guaranteed that the starting cell is free (i.e. contains .).

The robot will perform exactly $k$ operations. In each operation, if the cell in the direction the robot is facing (calculated as shown above) is within the map and is a free space, the robot moves to that cell. Otherwise, the robot stays in place and rotates $90^\circ$ to the right (i.e. its direction becomes $(d+1) \bmod 4$). Note that if the robot revisits a cell it has already been to, it is only counted once.

Your task is to determine how many distinct cells the robot visits (including the starting cell) after performing $k$ operations.

inputFormat

The first line contains three integers $n$, $m$, and $k$ $(1\le n,m\le 1000,\, 0\le k\le 10^9)$, representing the dimensions of the map and the number of operations, respectively.

The second line contains three integers $x_0$, $y_0$, and $d_0$ $(1\le x_0\le n,\, 1\le y_0\le m,\, 0\le d_0\le 3)$, representing the starting position and the initial direction of the robot.

The following $n$ lines each contain a string of length $m$ consisting only of characters . and x, representing the map. The character . denotes a free cell and x denotes an obstacle.

outputFormat

Output a single integer representing the number of distinct cells the robot has visited after $k$ operations.

sample

3 3 5
2 2 0
...
...
...

4