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<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define mk make_pair
int n,m,q,dis[8][8],inf;char s[100005],t[100005];
vector<int>vec[4];queue<pair<int,int> >Q;
void add(int i,int x,vector<int>&v){
	int sz=vec[i].size(),p=lower_bound(vec[i].begin(),vec[i].end(),x)-vec[i].begin();
	if(p)v.push_back(vec[i][p-1]);if(p<sz)v.push_back(vec[i][p]);
}
void upt(int x,int y,int z){
	if(dis[x][y]>z)dis[x][y]=z,Q.push(mk(x,y));
}
int main(){
	n=gi();m=gi();q=gi();scanf("%s%s",s+1,t+1);
	for(int i=1;i<=n;++i)vec[s[i]=='W'?0:1].push_back(i);
	for(int i=1;i<=m;++i)vec[t[i]=='N'?2:3].push_back(i);
	while(q--){
		int a=gi(),b=gi(),c=gi(),d=gi();vector<int>X,Y;
		for(int i=0;i<2;++i)add(i,a,X),add(i,c,X);
		for(int i=2;i<4;++i)add(i,b,Y),add(i,d,Y);
		sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
		sort(Y.begin(),Y.end());Y.erase(unique(Y.begin(),Y.end()),Y.end());
//		puts("x :");for(int x:X)printf("%d ",x);puts("");
//		puts("y :");for(int y:Y)printf("%d ",y);puts("");
		int lx=X.size(),ly=Y.size();
		int sx=lower_bound(X.begin(),X.end(),a)-X.begin();
		int sy=lower_bound(Y.begin(),Y.end(),b)-Y.begin();
		int tx=lower_bound(X.begin(),X.end(),c)-X.begin();
		int ty=lower_bound(Y.begin(),Y.end(),d)-Y.begin();
		memset(dis,63,sizeof(dis));inf=dis[0][0];dis[sx][sy]=0;Q.push(mk(sx,sy));
		while(!Q.empty()){
			int x=Q.front().first,y=Q.front().second;Q.pop();
//			printf("x=%d y=%d\n",x,y);
			if(s[X[x]]=='W')for(int z=y-1;z>=0;--z)upt(x,z,dis[x][y]+Y[y]-Y[z]);
			else for(int z=y+1;z<ly;++z)upt(x,z,dis[x][y]+Y[z]-Y[y]);
			if(t[Y[y]]=='N')for(int z=x-1;z>=0;--z)upt(z,y,dis[x][y]+X[x]-X[z]);
			else for(int z=x+1;z<lx;++z)upt(z,y,dis[x][y]+X[z]-X[x]);
		}
//		for(int i=0;i<lx;++i,puts(""))
//			for(int j=0;j<ly;++j)
//				printf("%d ",dis[i][j]==inf?-1:dis[i][j]);
		printf("%d\n",dis[tx][ty]==inf?-1:dis[tx][ty]);
	}
	return 0;
}