Problem: In Takaha-shi, the capital of Republic of AtCoder, there are N roads extending east and west, and M roads extending north and south. There are no other roads. The i-th east-west road from the north and the j-th north-south road from the west cross at the intersection (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 1.

Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string S of length N and a string T of length M, as follows:

* If the i-th character in S is `W`, one can only walk westward along the i-th east-west road from the north;
* If the i-th character in S is `E`, one can only walk eastward along the i-th east-west road from the north;
* If the i-th character in T is `N`, one can only walk northward along the i-th north-south road from the west;
* If the i-th character in T is `S`, one can only walk southward along the i-th south-west road from the west.



Process the following Q queries:

* In the i-th query, a_i, b_i, c_i and d_i are given. What is the minimum distance to travel to reach the intersection (c_i, d_i) from the intersection (a_i, b_i) by walking along the roads?

Constraints

* 2 \leq N \leq 100000
* 2 \leq M \leq 100000
* 2 \leq Q \leq 200000
* |S| = N
* S consists of `W` and `E`.
* |T| = M
* T consists of `N` and `S`.
* 1 \leq a_i \leq N
* 1 \leq b_i \leq M
* 1 \leq c_i \leq N
* 1 \leq d_i \leq M
* (a_i, b_i) \neq (c_i, d_i)

Input

Input is given from Standard Input in the following format:


N M Q
S
T
a_1 b_1 c_1 d_1
a_2 b_2 c_2 d_2
:
a_Q b_Q c_Q d_Q


Output

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

Examples

Input

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


Output

6
11
5
4


Input

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


Output

4
-1


Input

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


Output

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

Solution (in CPP):

Solution:
#include<cstdio>
#include<queue>
#include<algorithm>
#include<vector>
struct Edge{
    int u,v;
    long long c;
    Edge(int u,int v,long long c):u(u),v(v),c(c){}
};
struct Element{
    int start,end;
    Element(int s,int e):start(s),end(e){}
};
struct Node{
    int u;
    long long value;
    Node(int u,long long value):u(u),value(value){}
    bool operator <(const Node& other)const{
        return value>other.value;
    }
};
char s[100005], t[100005];
//0, 1: n,s/w,e
int lx[100005][2], rx[100005][2];
int ly[100005][2], ry[100005][2];
int needX[100005], needY[100005];
int row[10], col[10];
std::vector<Edge>g[105];
int vis[105]; long long dis[105];

void preWork(int n,int m){
	for(int i = 1; i <= n; i++){
		if(i!=1) lx[i][0] = lx[i-1][0], lx[i][1] = lx[i-1][1];
		else lx[i][0] = lx[i][1] = -1;
		if(s[i]=='W') lx[i][0] = i;
		else lx[i][1] = i;
	}
	for(int i = n; i >= 1; i--){
		if(i!=n) rx[i][0] = rx[i+1][0], rx[i][1] = rx[i+1][1];
		else rx[i][0] = rx[i][1] = -1;
		if(s[i]=='W') rx[i][0] = i;
		else rx[i][1] = i;
	}
	for(int i = 1; i <= m; i++){
		if(i!=1) ly[i][0] = ly[i-1][0], ly[i][1] = ly[i-1][1];
		else ly[i][0] = ly[i][1] = -1;
		if(t[i]=='N') ly[i][0] = i;
		else ly[i][1] = i;
	}
	for(int i = m; i >= 1; i--){
		if(i!=m) ry[i][0] = ry[i+1][0], ry[i][1] = ry[i+1][1];
		else ry[i][0] = ry[i][1] = -1;
		if(t[i]=='N') ry[i][0] = i;
		else ry[i][1] = i;
	}
}

long long max(long long a,long long b){ return a>b?a:b; }

long long min(long long a,long long b){ return a>b?b:a; }

Element buildGraph(int cntR,int cntC,int A,int B,int C,int D){
    std::sort(row+1,row+1+cntR);
    std::sort(col+1,col+1+cntC);
    /*for(int i = 1; i <= cntR; i++) printf("%d ",row[i]);
    printf("\n");
    for(int i = 1; i <= cntC; i++) printf("%d ",col[i]);
    printf("\n");*/
    int start = -1, end = -1;
    for(int i = 1; i <= cntR; i++){
        for(int j = 1; j <= cntC; j++){
            int id = (i-1)*cntC+j;
            g[id].clear();
            vis[id] = 0;
            dis[id] = 1e18+7;
            int r = row[i], c = col[j];
            if(s[r]=='W' && j!=1) g[id].push_back(Edge(id,(i-1)*cntC+j-1,c-col[j-1]));
            else if(s[r]=='E' && j!=cntC) g[id].push_back(Edge(id,(i-1)*cntC+j+1,col[j+1]-c));
            if(t[c]=='N' && i!=1) g[id].push_back(Edge(id,(i-2)*cntC+j,row[i]-row[i-1]));
            else if(t[c]=='S' && i!=cntR) g[id].push_back(Edge(id,(i)*cntC+j,row[i+1]-row[i]));
            if(r==A && c==B) start = id;
            else if(r==C && c==D) end = id;
        }
    }
    return Element(start,end);
}

long long dijkstra(int start,int end){
    std::priority_queue<Node>Q;
    dis[start] = 0;
    Q.push(Node(start,dis[start]));
    while(Q.size()!=0){
        while(Q.size()!=0 && vis[Q.top().u]==1) Q.pop();
        if(Q.size()==0) break;
        Node cur = Q.top(); Q.pop();
        int u = cur.u;
        vis[u] = 1;
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i].v;
            if(vis[v]==0 && dis[u]+g[u][i].c<dis[v]){
                dis[v] = dis[u]+g[u][i].c;
                Q.push(Node(v,dis[v]));
            }
        }
    }
    if(vis[end]) return dis[end];
    else return -1;
}

int main(){
	int n,m,q;
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s%s",s+1,t+1);
	preWork(n,m);
    while(q--){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        int cntR = 0, cntC = 0;
        for(int i = 0; i < 2; i++){
            if(lx[a][i]!=-1 && !needX[lx[a][i]]) row[++cntR] = lx[a][i], needX[lx[a][i]] = 1;
            if(rx[a][i]!=-1 && !needX[rx[a][i]]) row[++cntR] = rx[a][i], needX[rx[a][i]] = 1;
            if(lx[c][i]!=-1 && !needX[lx[c][i]]) row[++cntR] = lx[c][i], needX[lx[c][i]] = 1;
            if(rx[c][i]!=-1 && !needX[rx[c][i]]) row[++cntR] = rx[c][i], needX[rx[c][i]] = 1;
            if(ly[b][i]!=-1 && !needY[ly[b][i]]) col[++cntC] = ly[b][i], needY[ly[b][i]] = 1;
            if(ry[b][i]!=-1 && !needY[ry[b][i]]) col[++cntC] = ry[b][i], needY[ry[b][i]] = 1;
            if(ly[d][i]!=-1 && !needY[ly[d][i]]) col[++cntC] = ly[d][i], needY[ly[d][i]] = 1;
            if(ry[d][i]!=-1 && !needY[ry[d][i]]) col[++cntC] = ry[d][i], needY[ry[d][i]] = 1;
        }
        Element graph = buildGraph(cntR,cntC,a,b,c,d);
        printf("%lld\n",dijkstra(graph.start,graph.end));
        for(int i = 1; i <= cntR; i++) needX[row[i]] = 0;
        for(int i = 1; i <= cntC; i++) needY[col[i]] = 0;
    }
	return 0;
}