#exawizards2019f. [exawizards2019_f]More Realistic Manhattan Distance

[exawizards2019_f]More Realistic Manhattan Distance

Problem Statement

In Takaha-shi, the capital of Republic of AtCoder, there are NN roads extending east and west, and MM roads extending north and south. There are no other roads. The ii-th east-west road from the north and the jj-th north-south road from the west cross at the intersection (i,j)(i, j). Two east-west roads do not cross, nor do two north-south roads. The distance between two adjacent roads in the same direction is 11.

Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string SS of length NN and a string TT of length MM, as follows:

  • If the ii-th character in SS is W, one can only walk westward along the ii-th east-west road from the north;
  • If the ii-th character in SS is E, one can only walk eastward along the ii-th east-west road from the north;
  • If the ii-th character in TT is N, one can only walk northward along the ii-th north-south road from the west;
  • If the ii-th character in TT is S, one can only walk southward along the ii-th south-west road from the west.

Process the following QQ queries:

  • In the ii-th query, ai,bi,cia_i, b_i, c_i and did_i are given. What is the minimum distance to travel to reach the intersection (ci,di)(c_i, d_i) from the intersection (ai,bi)(a_i, b_i) by walking along the roads?

Constraints

  • 2leqNleq1000002 \\leq N \\leq 100000
  • 2leqMleq1000002 \\leq M \\leq 100000
  • 2leqQleq2000002 \\leq Q \\leq 200000
  • S=N|S| = N
  • SS consists of W and E.
  • T=M|T| = M
  • TT consists of N and S.
  • 1leqaileqN1 \\leq a_i \\leq N
  • 1leqbileqM1 \\leq b_i \\leq M
  • 1leqcileqN1 \\leq c_i \\leq N
  • 1leqdileqM1 \\leq d_i \\leq M
  • (ai,bi)neq(ci,di)(a_i, b_i) \\neq (c_i, d_i)

Input

Input is given from Standard Input in the following format:

NN MM QQ SS TT a1a_1 b1b_1 c1c_1 d1d_1 a2a_2 b2b_2 c2c_2 d2d_2 :: aQa_Q bQb_Q cQc_Q dQd_Q

Output

In the ii-th line, print the response to the ii-th query. If the intersection (ci,di)(c_i, d_i) cannot be reached from the intersection (ai,bi)(a_i, b_i) by walking along the roads, print -1 instead.


Sample Input 1

4 5 4
EEWW
NSNNS
4 1 1 4
1 3 1 2
4 2 3 2
3 3 3 5

Sample Output 1

6
11
5
4

The permitted direction for each road is shown in the following figure (north upward):

For each of the four queries, a route that achieves the minimum travel distance is as follows:


Sample Input 2

3 3 2
EEE
SSS
1 1 3 3
3 3 1 1

Sample Output 2

4
-1

The travel may be impossible.


Sample Input 3

9 7 10
EEEEEWEWW
NSSSNSN
4 6 9 2
3 7 6 7
7 5 3 5
1 1 8 1
4 3 5 4
7 4 6 4
2 5 8 6
6 6 2 7
2 4 7 5
7 2 9 7

Sample Output 3

9
-1
4
9
2
3
7
7
6
-1