Asteroid Field Escape

You are piloting a spaceship through an asteroid field represented as a grid. The grid cells may either be empty (denoted by '.') or contain an asteroid (denoted by '#'). Two special cells are marked: one as the starting point 'S' and the other as the exit 'E'.

Every m time units, the entire asteroid field reconfigures according to a transformation grid. For each cell that currently contains an asteroid ('#'), a direction is provided in the corresponding cell of the transformation grid. If the direction is given by one of the characters U, D, L, R, then the asteroid moves one cell in that direction. The grid wraps around both horizontally and vertically. Formally, if an asteroid is at cell \( (i,j) \) and the instruction is d, then its new position \( (i',j') \) is given by: \[ (i',j') = \begin{cases} ((i-1+r)\bmod r, \; j) & \text{if } d = U,\\ ((i+1)\bmod r, \; j) & \text{if } d = D,\\ (i, \; (j-1+c)\bmod c) & \text{if } d = L,\\ (i, \; (j+1)\bmod c) & \text{if } d = R. \end{cases} \] Note that only cells that originally contained an asteroid are transformed; all other cells remain unchanged.

Your task is to compute the minimum time required for the spaceship to reach the exit. The spaceship can move one cell per time unit (up, down, left, or right) without moving diagonally, and it cannot move into a cell occupied by an asteroid. At each time step, the grid state is determined as follows:

• At time 0, the grid is the initial configuration.
• If the current time t > 0 is a multiple of m (i.e. \( t \bmod m = 0 \)), then the grid is replaced by its transformed version (computed from the initial grid using the transformation rules).
• Otherwise, the grid remains the same as the initial configuration.

If it is impossible to reach the exit, output -1.

inputFormat

The first line of input contains three integers separated by spaces: r c m, where r is the number of rows, c is the number of columns, and m is the time interval for grid reconfiguration.

The next r lines each contain a string of length c representing the initial grid configuration. Each character is one of 'S', 'E', '.', or '#'.

The following r lines each contain a string of length c representing the transformation grid. Each character is one of 'U', 'D', 'L', or 'R'.

outputFormat

Output a single integer: the minimum time required for the spaceship to reach the exit, or -1 if it is impossible.

## sample

4 4 2
S..#
....
.#..
..E#
DUDU
RLUD
LRLU
UDUD

5