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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
typedef pair<int,pint> tint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int ne[100100],nw[100100],se[100100],sw[100100];
int en[100100],es[100100],wn[100100],Ws[100100];
string s,t;
int h,w,inf=11451419;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int gr[10][10][4];
int dp[10][10];
bool sumi[10][10];
priority_queue<tint> q;
void aedge(int x,int y,int z){
	if(dp[x][y]<=z) return;
	dp[x][y]=z;
	q.push(mp(-z,mp(x,y)));
}
int cal(int sx,int sy,int gx,int gy){
	vector<int> ta,yo,t2,y2;
	ta.pb(en[gy]);ta.pb(es[gy]);ta.pb(wn[gy]);ta.pb(Ws[gy]);
	yo.pb(ne[gx]);yo.pb(nw[gx]);yo.pb(se[gx]);yo.pb(sw[gx]);
	ta.pb(en[sy]);ta.pb(es[sy]);ta.pb(wn[sy]);ta.pb(Ws[sy]);
	yo.pb(ne[sx]);yo.pb(nw[sx]);yo.pb(se[sx]);yo.pb(sw[sx]);
	sort(All(ta));ta.erase(unique(All(ta)),ta.end());
	sort(All(yo));yo.erase(unique(All(yo)),yo.end());
	rep(i,ta.size()){
		if(ta[i]>=0 && ta[i]<inf) t2.pb(ta[i]);
	}
	rep(i,yo.size()){
		if(yo[i]>=0 && yo[i]<inf) y2.pb(yo[i]);
	}
	rep(i,8) rep(j,8){
		dp[i][j]=inf;
		rep(k,4) gr[i][j][k]=inf;
	}
	memset(sumi,false,sizeof(sumi));
	int n=y2.size(),m=t2.size();
	rep(i,n) rep(j,m){
		if(s[y2[i]]=='E' && j<m-1) gr[i][j][1]=t2[j+1]-t2[j];
		if(s[y2[i]]=='W' && j>0) gr[i][j][3]=t2[j]-t2[j-1];
		if(t[t2[j]]=='N' && i>0) gr[i][j][0]=y2[i]-y2[i-1];
		if(t[t2[j]]=='S' && i<n-1) gr[i][j][2]=y2[i+1]-y2[i];
	}
	aedge(lower_bound(All(y2),sx)-y2.begin(),lower_bound(All(t2),sy)-t2.begin(),0);
	while(!q.empty()){
		tint p=q.top();q.pop();int x=p.se.fi,y=p.se.se,z=-p.fi;
		if(sumi[x][y]) continue;sumi[x][y]=true;
		//cout<<y2[x]<<' '<<t2[y]<<' '<<dp[x][y]<<endl;
		rep(i,4){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=0 && nx<n && ny>=0 && ny<m){
				aedge(nx,ny,dp[x][y]+gr[x][y][i]);
			}
		}
	}
	return dp[lower_bound(All(y2),gx)-y2.begin()][lower_bound(All(t2),gy)-t2.begin()];
}
int main()
{
	int q,sx,sy,gx,gy;
	cin>>h>>w>>q;
	cin>>s;
	cin>>t;
	ne[0]=nw[0]=-1;
	rep(i,h){
		if(s[i]=='E') ne[i]=i;else nw[i]=i;
		ne[i+1]=ne[i];nw[i+1]=nw[i];
	}
	se[h-1]=sw[h-1]=inf;
	for(int i=h-1;i>=0;i--){
		if(s[i]=='E') se[i]=i;else sw[i]=i;
		if(i>0) se[i-1]=se[i],sw[i-1]=sw[i];
	}
	wn[0]=Ws[0]=-1;
	rep(i,w){
		if(t[i]=='N') wn[i]=i;else Ws[i]=i;
		wn[i+1]=wn[i];Ws[i+1]=Ws[i];
	}
	en[w-1]=es[w-1]=inf;
	for(int i=w-1;i>=0;i--){
		if(t[i]=='N') en[i]=i;else es[i]=i;
		if(i>0) en[i-1]=en[i],es[i-1]=es[i];
	}
	rep(i,q){
		cin>>sx>>sy>>gx>>gy;
		sx--;sy--;gx--;gy--;
		int ret=cal(sx,sy,gx,gy);
		if(ret>=inf) cout<<-1<<endl;else cout<<ret<<endl;
	}
}