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;
#define nn 400008
#define pii pair<int,int>
#define mp make_pair
int n,m;int q;pii from[nn],dest[nn];
int ans[nn];
int dir[2][nn];
vector<int> path[2][2];
/*
0...
....
...1

0->
1|
*/
int lb(int x,vector<int> &v) {if(v.size()==0  or v[0]>x) return 0;return v[upper_bound(v.begin(),v.end(),x)-v.begin()-1];}
int ub(int x,vector<int> &v) {if(v.size()==0 or v[v.size()-1]<x) return 0;return v[lower_bound(v.begin(),v.end(),x)-v.begin()];}
int lb2(int x,vector<int> &v) {if(v.size()==0 or v[0]>x) return 1e8;return x-lb(x,v);}
int ub2(int x,vector<int> &v) {if(v.size()==0 or v[v.size()-1]<x) return 1e8;return ub(x,v)-x;}
int bet(int l,int r,vector<int> &v) {return (ub(l,v) and ub(l,v)<=r);}

void solve()
{
	path[0][0].clear(),path[0][1].clear(),path[1][0].clear(),path[1][1].clear();
	for(int i=1;i<=n;i++) path[0][dir[0][i]].push_back(i);for(int i=1;i<=m;i++) path[1][dir[1][i]].push_back(i);
 	
	
	for(int i=1;i<=q;i++)
	{pii s=from[i],t=dest[i];
		if(s.first==t.first and dir[0][s.first]==s.second<t.second) ans[i]=0;
		if(s.second==t.second and dir[1][s.second]==s.first<t.first) ans[i]=0;
		if(s.first<=t.first and s.second<=t.second)
		{
			int me=0,me2=0,ms=0,ms2=0;
			if(!dir[0][s.first])me=lb2(s.first,path[0][1])+lb2(s.second,path[1][0]);
			if(!dir[1][s.second])ms=lb2(s.first,path[0][0])+lb2(s.second,path[1][1]);
			
			if(!dir[0][t.first])me2=ub2(t.first,path[0][1])+ub2(t.second,path[1][0]);
			if(!dir[1][t.second])ms2=ub2(t.first,path[0][0])+ub2(t.second,path[1][1]);
			
			ans[i]=min(ans[i],me+ms2);ans[i]=min(ans[i],ms+me2);
			if(bet(s.first,t.first,path[0][1])) ans[i]=min(ans[i],ms+ms2);
			if(bet(s.second,t.second,path[1][1])) ans[i]=min(ans[i],me+me2);
			
			if(dir[1][s.second] and dir[1][t.second])
				if(bet(s.second,t.second,path[1][0]))
					ans[i]=min(ans[i],lb2(s.first,path[0][1])+ub2(s.first,path[0][1]));
			
			if(dir[0][s.first] and dir[0][t.first])
				if(bet(s.first,t.first,path[0][0]))
					ans[i]=min(ans[i],lb2(s.second,path[1][1])+ub2(s.second,path[1][1]));
		}
	} 
 	
	 	
}


void transform(int mask)
{
	for(int i=1;i<=n;i++) if(mask&1) dir[0][i]^=1;
	if(mask&2) reverse(dir[0]+1,dir[0]+n+1);
	for(int i=1;i<=m;i++) if(mask&2) dir[1][i]^=1;
	if(mask&1) reverse(dir[1]+1,dir[1]+m+1);
	
	for(int i=1;i<=q;i++)
	{
		if(mask&2) 
		{
			from[i].first=n-from[i].first+1;
			dest[i].first=n-dest[i].first+1;
		}
		if(mask&1)
		{
			from[i].second=m-from[i].second+1;
			dest[i].second=m-dest[i].second+1;
		}
	}
}
char buf[nn];
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s",buf+1);for(int i=1;i<=n;i++) dir[0][i]=(buf[i]=='E');
	scanf("%s",buf+1);for(int i=1;i<=m;i++) dir[1][i]=(buf[i]=='S');
	for(int i=1;i<=q;i++) ans[i]=1e9,scanf("%d%d%d%d",&from[i].first,&from[i].second,&dest[i].first,&dest[i].second);	
	
	for(int i=0;i<4;i++) {transform(i);solve();transform(i);}	
	
	for(int i=1;i<=q;i++) if(ans[i]<1e7)printf("%d\n",ans[i]*2+abs(from[i].first-dest[i].first)+abs(from[i].second-dest[i].second));else printf("%d\n",-1);
	return 0;
}