jzh has an $n \times m$ maze, where each cell contains a reflector. The type of reflector can be one of the following two:

1. / (right-leaning reflector):

   • Ball enters from the left $\to$ reflects upwards
   • Ball enters from the right $\to$ reflects downwards
   • Ball enters from above $\to$ reflects to the left
   • Ball enters from below $\to$ reflects to the right

2. \ (left-leaning reflector):

   • Ball enters from the left $\to$ reflects downwards
   • Ball enters from the right $\to$ reflects upwards
   • Ball enters from above $\to$ reflects to the right
   • Ball enters from below $\to$ reflects to the left

The maze is surrounded by rectangular reflectors. If the ball hits a reflector on the boundary of the maze perpendicularly, it will return along its original path.

Djangle has two hammers. He can smash at most two reflectors at any time during the ball's movement (he can use a reflector to bounce first and then smash it). When the ball passes through a smashed reflector, it will not reflect.

Smashing the reflector at row $i$, column $j$ costs $a_{i,j}$ stamina.

Note: Djangle can use two hammers, one hammer, or no hammers at all.

gsh finds this process interesting and wants to know: if a ball is launched from a cell in a certain direction, can it reach another cell? If it can, what is the minimum stamina Djangle needs to spend?

Input

The first line contains three integers $n, m, q$ ($1 \le n, m \le 10^5$, $1 \le n \times m \le 4 \times 10^6$, $1 \le q \le 10^6$), representing the number of rows, columns, and queries, respectively.

The next $n$ lines, each containing $m$ characters $S_{i,j} \in \{\backslash, /\}$, represent the reflector type at row $i$, column $j$.

The next $n$ lines, each containing $m$ positive integers, represent $a_{i,j}$ ($1 \le a_{i,j} \le 10^9$).

The next $q$ lines, each containing five space-separated query parameters: Starting coordinates: $(startx, starty)$. Launch direction: $direction \in \{N, S, W, E\}$ representing North (up), South (down), West (left), and East (right), respectively. Target coordinates: $(endx, endy)$.

$1 \le startx, endx \le n, 1 \le starty, endy \le m$.

Output

For each query, output a single integer representing the minimum stamina Djangle needs to spend. If the ball cannot reach the target cell under any circumstances, output $-1$.

Examples

Input 1

2 3 1
/\ \
///
2 3 1
4 6 5
1 1 E 2 3

Output 1

3

Note

For Example 1:

Figure 1. Reflector reflection rules

Input 2

3 3 5
\\\
\/\
/\\
3 1 1
1 4 1
2 5 1
1 3 N 1 2
3 3 S 2 3
2 3 W 2 3
3 1 S 1 2
2 2 S 1 2

Output 2

1
0
0
3
1