Problem Description

There is a grid of squares with $ N $ rows and $ M $ columns. The square at the $ i $th row from the top and the $ j $th column from the left is represented by $ (i,j) $. In particular, the top-left square is $ (1,1) $ and the bottom-right square is $ (N,M) $.

The state of the grid is represented by a 2D array $ s $, where $ s_{ij} $ is # if there is an obstacle on the square $ (i,j) $, and . or S or G if there is no obstacle.

The robot starts at the square marked with S at time $ 0 $ and attempts to reach the square marked with G in the shortest possible time.

However, the robot cannot move in all directions at all times.

A string $ d $ of length $ K $ is given. Each second, the robot can either move to an adjacent square or stay in the current square. However, from time $ t $ to $ t+1 $, the robot can only move one square in the direction specified by $ d_{r+1} $, where $ r $ is the remainder of $ t $ divided by $ K $ ($0 \leq r \leq K-1$). If the current square is $ (i,j) $, and $ d_{r+1} $ is U, the robot can move to $ (i-1,j) $; if it is D, to $ (i+1,j) $; if it is L, to $ (i,j-1) $; and if it is R, to $ (i,j+1) $. Moving outside the grid or into a square with an obstacle is not allowed.

Find the shortest time for the robot to reach the square marked with G from the square marked with S under these conditions.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ d_{1}...d_{K} $ $ s_{11}...s_{1M} $ $ : $ $ s_{N1}...s_{NM} $

Output Format

Output the shortest time for the robot to move from S to G. If it is impossible to move from S to G by any means, output $ -1 $.

Sample Input and Output

Sample Input #1

2 3 5
UDRRL
S..
.#G

Sample Output #1

7

Sample Input #2

3 3 5
UDUDD
S..
...
.G.

Sample Output #2

-1

Sample Input #3

3 3 5
UDLRD
S..
.#.
..G

Sample Output #3

12

Notes/Hints

Constraints

• $2 \leq N,M \leq 1000$
• $1 \leq K \leq 100000$
• $ s $ consists of #, ., S, or G
• There is exactly one square marked with S and one marked with G
• The length of $ d $ is $ K $
• $ d $ consists of U, D, L, or R
• $ N,M,K $ are integers

Sample Explanation 2

No matter how the robot moves, it cannot move to the second column.

见题面 Input 部分

见题面 Output 部分