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 <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

int main(){
	int N,M,Q; cin >> N >> M >> Q;
	string S,T; cin >> S; cin >> T;
	vector<int> ln(M+2,-1e9),rn(M+2,1e9),ls(M+2,-1e9),rs(M+2,1e9);
	vector<int> ue(N+2,-1e9),de(N+2,1e9),uw(N+2,-1e9),dw(N+2,1e9);
	repp(i,0,M){
		ln[i+1] = ln[i]; ls[i+1] = ls[i];
		if(T[i] == 'N') ln[i+1] = i+1;
		else ls[i+1] = i+1;
	}
	repm(i,M,0){
		rn[i] = rn[i+1]; rs[i] = rs[i+1];
		if(T[i-1] == 'N') rn[i] = i;
		else rs[i] = i;
	}
	repp(i,0,N){
		ue[i+1] = ue[i]; uw[i+1] = uw[i];
		if(S[i] == 'E') ue[i+1] = i+1;
		else uw[i+1] = i+1;
	}
	repm(i,N,0){
		de[i] = de[i+1]; dw[i] = dw[i+1];
		if(S[i-1] == 'E') de[i] = i;
		else dw[i] = i;
	}
	repp(rep_q,0,Q){
		int a,b,c,d; cin >> a >> b >> c >> d;
		vector<int> v(6),h(6);
		h[0] = a; v[0] = b; h[5] = c; v[5] = d;
		if(S[a-1] == 'E'){
			h[1] = uw[a]; h[2] = dw[a];
		} else {
			h[1] = ue[a]; h[2] = de[a];
		}
		if(S[c-1] == 'E'){
			h[3] = uw[c]; h[4] = dw[c];
		} else {
			h[3] = ue[c]; h[4] = de[c];
		}
		if(T[b-1] == 'N'){
			v[1] = ls[b]; v[2] = rs[b];
		} else {
			v[1] = ln[b]; v[2] = rn[b];
		}
		if(T[d-1] == 'N'){
			v[3] = ls[d]; v[4] = rs[d];
		} else {
			v[3] = ln[d]; v[4] = rn[d];
		}
		vector<vector<int>> ans(6,vector<int>(6,1e8)),p(6,vector<int>(6,0));
		ans[0][0] = 0;
		int x = 0, y = 0;
		while(x != -1){
			p[x][y] = 1;
			int xx = -1, yy = -1, zz = 1e8;
			repp(i,0,6) repp(j,0,6) if(!p[i][j]){
				if(h[x] == h[i] && h[x] > 0 && h[x] <= N && (((S[h[x]-1]=='W')^(v[y]<v[j])) || v[y] == v[j])) ans[i][j] = min(ans[i][j],ans[x][y]+abs(v[j]-v[y]));
				if(v[y] == v[j] && v[y] > 0 && v[y] <= M && (((T[v[y]-1]=='N')^(h[x]<h[i])) || h[x] == h[i])) ans[i][j] = min(ans[i][j],ans[x][y]+abs(h[i]-h[x]));
				if(zz > ans[i][j]){
					xx = i; yy = j; zz = ans[i][j];
				}
			}
			x = xx; y = yy;
		}
		cout << (ans[5][5]==1e8?-1:ans[5][5]) << endl;
	}
	return 0;
}