An ant walks on an R by C grid that wraps around at every edge (a torus): stepping off the top re-enters at the bottom, off the left re-enters at the right, and so on. Every cell starts white. The ant starts on a given cell facing one of N, E, S, W, and performs T steps. Each step:
- If the current cell is white: turn 90 degrees right (clockwise), flip the cell to black, then move forward one cell.
- If the current cell is black: turn 90 degrees left (counter-clockwise), flip the cell to white, then move forward one cell.
Here N decreases the row, S increases the row, E increases the column, W decreases the column. After T steps, count the black cells.
Input format
Line 1: two integers R and C.
Line 2: r0 c0 D T - the start cell, the facing letter D (N/E/S/W), and the number of steps T.
Output format
A single integer: the number of black cells after T steps.
Constraints
- 2 <= R, C <= 100
- 0 <= r0 <= R-1, 0 <= c0 <= C-1
- 0 <= T <= 1000000