Haunted House (part 2)

Note: This problem statement is identical to Haunted House (part 1), but includes an additional magical bell.

You’re in a haunted house with corridors and walls. Your goal is to get from S (start) to E (exit) while avoiding ghosts that roam the house.

The house is an $N \times M$ grid:

'S' — your starting cell (exactly one).
'E' — the exit (exactly one).
'.' — empty floor (you can walk here).
'X' — wall (you cannot enter).

There are $K$ ghosts. Each ghost starts at some given cell (r, c) and moves in one of the four directions (up, down, left, right), without ever changing course.

Ghosts can do a lot of stuff that you can't. Specifically, ghosts ignore inner walls (they can pass through 'X'). Also, when they reach an outer wall, they wrap around the corresponding row or column:

A ghost moving up from row 0 goes to row N-1.
A ghost moving down from row N-1 goes to row 0.
A ghost moving left from col 0 goes to col M-1.
A ghost moving right from col M-1 goes to col 0.

All ghosts move one cell per second, simultaneously. You also move one cell per second (up, down, left, right), or you may wait in place.

In addition, you possess a magical bell that can be used $B$ times. When you ring the bell, all the ghosts in the house stop moving for $S$ seconds. The bell effects are cumulative; e.g., ringing the bell twice in a row stops the ghosts for $2 \cdot S$ seconds. Ringing the bell takes 0 seconds. The bell can only be rung at integer times.

There are two ways to collide with a ghost:

If at the end of a second, you and the ghost occupy the same cell.
If you pass through a ghost (you move A→B while the ghost moves B→A).

Your task: find the minimum time (in seconds) to reach E from S without ever colliding with a ghost.

Input

The first line contains an integer $T$ — the number of test cases.

For each test case:

A line with five integers $N, M, K, B, S$ ( $2 \leq N, M \leq 30$ , $0 \leq K \leq 50$ , $1 \leq B, S \leq 5$ ).
$N$ lines of length $M$ describing the house with characters from {S, E, ., X}.
All characters are uppercase; S and E appear exactly once; S and E are not on walls.
$K$ lines with ghost info: r c d
- $0 \leq r < N$ , $0 \leq c < M$
- $d \in U, D, L, R$
- No ghost will start where S is located.

Test cases will be separated by a ===== string.

Output

For each test case, print a single line Case #i: t, where t is the minimum number of seconds to reach E from S without collision, or -1 if it’s impossible.

Example

Input

2
3 3 1 1 1
S..
.X.
..E
1 2 D
=====
4 5 2 1 2
S...E
.XXX.
.....
....X
0 2 L
2 2 L

Output

Case #1: 4
Case #2: 11

Explanation

Case 1. If you don't ring the bell, the ghost will block your path and make you wait to be able to reach the exit. However, if you ring the bell at any point on your path, you will reach the exit when the ghost is not there.

Case 2. Without the bell, this escape would take you 14 seconds. With the bell, one of the optimal strategies would be:

t=0: (0,0)
t=1: (0,0) - wait 1 second
t=2: (1,0)
t=3: (2,0)
t=4: (3,0)
t=5: (3,1)
t=6: (3,2)
t=7: (2,2) - ring the bell at t=7 (before moving to (2,3)); ghosts are now frozen until t=9
t=8: (2,3)
t=9: (2,4)
t=10: (1,4) - you move up at the same time as the ghost in row 2 resumes moving and enters cell (2,4)
t=11: (0,4)