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 <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <string>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <deque>
#include <cmath>
#include <cassert>
#define SIZE 200005
#define INF 1000000000

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

char S[SIZE],T[SIZE];
int A[SIZE],B[SIZE],C[SIZE],D[SIZE];
int dw[SIZE],de[SIZE],dw2[SIZE],de2[SIZE];
int ds[SIZE],dn[SIZE],ds2[SIZE],dn2[SIZE];
int rs[SIZE],re[SIZE];
int ans[SIZE];
int n,m,q;

//South : +1
//East  : +1
void solve()
{
	for(int i=0;i<m;i++)
	{
		dw[i]=de[i]=-1;
		if(i>0)
		{
			if(dw[i-1]!=-1) dw[i]=dw[i-1]+1;
			if(de[i-1]!=-1) de[i]=de[i-1]+1;
		}
		if(T[i]=='E') de[i]=0;
		else dw[i]=0;
	}
	for(int i=m-1;i>=0;i--)
	{
		dw2[i]=de2[i]=-1;
		if(i+1<m)
		{
			if(dw2[i+1]!=-1) dw2[i]=dw2[i+1]+1;
			if(de2[i+1]!=-1) de2[i]=de2[i+1]+1;
		}
		if(T[i]=='E') de2[i]=0;
		else dw2[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		ds[i]=dn[i]=-1;
		if(i>0)
		{
			if(ds[i-1]!=-1) ds[i]=ds[i-1]+1;
			if(dn[i-1]!=-1) dn[i]=dn[i-1]+1;
		}
		if(S[i]=='S') ds[i]=0;
		else dn[i]=0;
	}
	for(int i=n-1;i>=0;i--)
	{
		ds2[i]=dn2[i]=-1;
		if(i+1<n)
		{
			if(ds2[i+1]!=-1) ds2[i]=ds2[i+1]+1;
			if(dn2[i+1]!=-1) dn2[i]=dn2[i+1]+1;
		}
		if(S[i]=='S') ds2[i]=0;
		else dn2[i]=0;
	}
	for(int i=0;i<n;i++)
	{
		rs[i]=(S[i]=='S');
		if(i>0) rs[i]+=rs[i-1];
	}
	for(int i=0;i<m;i++)
	{
		re[i]=(T[i]=='E');
		if(i>0) re[i]+=re[i-1];
	}
	for(int i=0;i<q;i++)
	{
		if(A[i]<=C[i]&&B[i]<=D[i])
		{
			ans[i]=-1;
			if(A[i]==C[i]&&S[A[i]]=='S') ans[i]=D[i]-B[i];
			else if(B[i]==D[i]&&T[B[i]]=='E') ans[i]=C[i]-A[i];
			else
			{
				int ms=-1;
				if(S[A[i]]=='S') ms=0;
				else if(dw[B[i]]!=-1&&ds[A[i]]!=-1) ms=(dw[B[i]]+ds[A[i]])*2;
				int me=-1;
				if(T[B[i]]=='E') me=0;
				else if(de[B[i]]!=-1&&dn[A[i]]!=-1) me=(de[B[i]]+dn[A[i]])*2;
				int ms2=-1;
				if(S[C[i]]=='S') ms2=0;
				else if(dw2[D[i]]!=-1&&ds2[C[i]]!=-1) ms2=(dw2[D[i]]+ds2[C[i]])*2;
				int me2=-1;
				if(T[D[i]]=='E') me2=0;
				else if(de2[D[i]]!=-1&&dn2[C[i]]!=-1) me2=(de2[D[i]]+dn2[C[i]])*2;
				int now=INF;
				if(ms>=0&&me2>=0) now=min(now,ms+me2+C[i]+D[i]-A[i]-B[i]);
				if(me>=0&&ms2>=0) now=min(now,me+ms2+C[i]+D[i]-A[i]-B[i]);
				int cs=rs[C[i]]-(A[i]==0?0:rs[A[i]-1]);
				int ce=re[D[i]]-(B[i]==0?0:re[B[i]-1]);
				if(me>=0&&me2>=0&&cs>0) now=min(now,me+me2+C[i]+D[i]-A[i]-B[i]);
				if(ms>=0&&ms2>=0&&ce>0) now=min(now,ms+ms2+C[i]+D[i]-A[i]-B[i]);
				
				if(T[B[i]]=='E'&&T[D[i]]=='E')
				{
					//printf("%d %d %d\n",ds2[A[i]],dw2[B[i]],ds[A[i]]);
					if(ds2[A[i]]!=-1&&dw2[B[i]]!=-1&&B[i]+dw2[B[i]]<D[i]&&ds[A[i]]!=-1)
					{
						now=min(now,ds2[A[i]]*2+ds[A[i]]*2+C[i]+D[i]-A[i]-B[i]);
					}
				}
				if(S[A[i]]=='S'&&S[C[i]]=='S')
				{
					if(de2[B[i]]!=-1&&dn2[A[i]]!=-1&&A[i]+dn2[A[i]]<C[i]&&de[B[i]]!=-1)
					{
						now=min(now,de2[B[i]]*2+de[B[i]]*2+C[i]+D[i]-A[i]-B[i]);
					}
				}
				
				if(now!=INF) ans[i]=now;
			}
			//printf("* %d %d %d %d\n",A[i],B[i],C[i],D[i]);
			//printf("%s %s -> %d\n",S,T,ans[i]);
		}
	}
}
int main()
{
	scanf("%d %d %d",&n,&m,&q);
	scanf("%s",&S);
	scanf("%s",&T);
	for(int i=0;i<n;i++)
	{
		if(S[i]=='E') S[i]='S';
		else S[i]='N';
	}
	for(int i=0;i<m;i++)
	{
		if(T[i]=='S') T[i]='E';
		else T[i]='W';
	}
	for(int i=0;i<q;i++)
	{
		scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
		A[i]--,B[i]--,C[i]--,D[i]--;
	}
	solve();
	for(int l=0,r=n-1;l<r;l++,r--) swap(S[l],S[r]);
	for(int i=0;i<m;i++)
	{
		if(T[i]=='E') T[i]='W';
		else T[i]='E';
	}
	for(int i=0;i<q;i++) A[i]=n-A[i]-1,C[i]=n-C[i]-1;
	solve();
	for(int l=0,r=m-1;l<r;l++,r--) swap(T[l],T[r]);
	for(int i=0;i<n;i++)
	{
		if(S[i]=='N') S[i]='S';
		else S[i]='N';
	}
	for(int i=0;i<q;i++) B[i]=m-B[i]-1,D[i]=m-D[i]-1;
	solve();
	for(int l=0,r=n-1;l<r;l++,r--) swap(S[l],S[r]);
	for(int i=0;i<m;i++)
	{
		if(T[i]=='E') T[i]='W';
		else T[i]='E';
	}
	for(int i=0;i<q;i++) A[i]=n-A[i]-1,C[i]=n-C[i]-1;
	solve();
	for(int i=0;i<q;i++) printf("%d\n",ans[i]);
	return 0;
}