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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <cstring>
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <list>  
#include <cassert>
#include <ctime>
#include <climits>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;
typedef unsigned long long ull;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a%b); }

const int MAXH=100000;
const int MAXW=100000;
const int MAXQ=200000;

int h,w,nq;
char hordir[MAXH+1];
char vertdir[MAXW+1];
int qsx[MAXQ],qsy[MAXQ],qtx[MAXQ],qty[MAXQ],qans[MAXQ];

bool qdone[MAXQ];
int prvlt[MAXH],prvrt[MAXH],nxtlt[MAXH],nxtrt[MAXH];
int prvup[MAXW],prvdn[MAXW],nxtup[MAXW],nxtdn[MAXW];

int calc(int sx,int sy,int tx,int ty,const vector<int> &xval,const vector<int> &yval) {
	//printf("calc (%d,%d)-(%d,%d) xval:",sx,sy,tx,ty); REPSZ(i,xval) printf(" %d",xval[i]); printf(" yval:"); REPSZ(i,yval) printf(" %d",yval[i]); puts("");
	int nx=SZ(xval),ny=SZ(yval);
	vector<vector<int>> d(nx,vector<int>(ny,INT_MAX));
	priority_queue<pair<int,pair<int,int>>> pq;
	REP(x,nx) REP(y,ny) if(xval[x]==sx&&yval[y]==sy) d[x][y]=0,pq.push(MP(-d[x][y],MP(x,y)));
	while(!pq.empty()) {
		int cost=-pq.top().first,x=pq.top().second.first,y=pq.top().second.second; pq.pop();
		if(cost!=d[x][y]) continue;
		//printf("\t(%d,%d)=%d\n",xval[x],yval[y],cost);
		REP(xx,nx) {
			if(xx<x&&vertdir[yval[y]]=='S'||xx>x&&vertdir[yval[y]]=='N') continue;
			int ncost=cost+abs(xval[x]-xval[xx]); if(ncost<d[xx][y]) d[xx][y]=ncost,pq.push(MP(-d[xx][y],MP(xx,y)));
		}
		REP(yy,ny) {
			if(yy<y&&hordir[xval[x]]=='E'||yy>y&&hordir[xval[x]]=='W') continue;
			int ncost=cost+abs(yval[y]-yval[yy]); if(ncost<d[x][yy]) d[x][yy]=ncost,pq.push(MP(-d[x][yy],MP(x,yy)));
		}
	}
	int ret=INT_MAX; REP(x,nx) REP(y,ny) if(xval[x]==tx&&yval[y]==ty) ret=min(ret,d[x][y]); return ret;
}

void solve() {
	REP(i,nq) qdone[i]=false;
	REP(invhor,2) {
		REP(invvert,2) {
			REP(x,h) prvlt[x]=hordir[x]=='W'?x:x==0?-1:prvlt[x-1];
			REP(x,h) prvrt[x]=hordir[x]=='E'?x:x==0?-1:prvrt[x-1];
			for(int x=h-1;x>=0;--x) nxtlt[x]=hordir[x]=='W'?x:x+1==h?-1:nxtlt[x+1];
			for(int x=h-1;x>=0;--x) nxtrt[x]=hordir[x]=='E'?x:x+1==h?-1:nxtrt[x+1];
			REP(y,w) prvup[y]=vertdir[y]=='N'?y:y==0?-1:prvup[y-1];
			REP(y,w) prvdn[y]=vertdir[y]=='S'?y:y==0?-1:prvdn[y-1];
			for(int y=w-1;y>=0;--y) nxtup[y]=vertdir[y]=='N'?y:y+1==w?-1:nxtup[y+1];
			for(int y=w-1;y>=0;--y) nxtdn[y]=vertdir[y]=='S'?y:y+1==w?-1:nxtdn[y+1];
			
			REP(i,nq) if(qsx[i]<=qtx[i]&&qsy[i]<=qty[i]&&!qdone[i]) {
				vector<int> usehor,usevert;
				if(prvlt[qsx[i]]!=-1) usehor.PB(prvlt[qsx[i]]);
				if(prvrt[qsx[i]]!=-1) usehor.PB(prvrt[qsx[i]]);
				if(nxtlt[qtx[i]]!=-1) usehor.PB(nxtlt[qtx[i]]);
				if(nxtrt[qtx[i]]!=-1) usehor.PB(nxtrt[qtx[i]]);
				if(qsx[i]!=qtx[i]&&nxtlt[qsx[i]+1]!=-1&&nxtlt[qsx[i]+1]<qtx[i]) usehor.PB(nxtlt[qsx[i]+1]);
				if(qsx[i]!=qtx[i]&&nxtrt[qsx[i]+1]!=-1&&nxtrt[qsx[i]+1]<qtx[i]) usehor.PB(nxtrt[qsx[i]+1]);
				if(prvup[qsy[i]]!=-1) usevert.PB(prvup[qsy[i]]);
				if(prvdn[qsy[i]]!=-1) usevert.PB(prvdn[qsy[i]]);
				if(nxtup[qty[i]]!=-1) usevert.PB(nxtup[qty[i]]);
				if(nxtdn[qty[i]]!=-1) usevert.PB(nxtdn[qty[i]]);
				if(qsy[i]!=qty[i]&&nxtup[qsy[i]+1]!=-1&&nxtup[qsy[i]+1]<qty[i]) usevert.PB(nxtup[qsy[i]+1]);
				if(qsy[i]!=qty[i]&&nxtdn[qsy[i]+1]!=-1&&nxtdn[qsy[i]+1]<qty[i]) usevert.PB(nxtdn[qsy[i]+1]);
				sort(usehor.begin(),usehor.end()); sort(usevert.begin(),usevert.end()); usehor.erase(unique(usehor.begin(),usehor.end()),usehor.end()); usevert.erase(unique(usevert.begin(),usevert.end()),usevert.end());
				qans[i]=calc(qsx[i],qsy[i],qtx[i],qty[i],usehor,usevert);
				qdone[i]=true;
			}
			reverse(vertdir,vertdir+w); REP(x,h) if(hordir[x]=='E') hordir[x]='W'; else if(hordir[x]=='W') hordir[x]='E'; REP(i,nq) qsy[i]=w-qsy[i]-1,qty[i]=w-qty[i]-1;
		}
		reverse(hordir,hordir+h); REP(y,w) if(vertdir[y]=='S') vertdir[y]='N'; else if(vertdir[y]=='N') vertdir[y]='S'; REP(i,nq) qsx[i]=h-qsx[i]-1,qtx[i]=h-qtx[i]-1;
	}
}

void run() {
	scanf("%d%d%d",&h,&w,&nq);
	scanf("%s",hordir);
	scanf("%s",vertdir);
	REP(i,nq) scanf("%d%d%d%d",&qsx[i],&qsy[i],&qtx[i],&qty[i]),--qsx[i],--qsy[i],--qtx[i],--qty[i];
	solve();
	REP(i,nq) printf("%d\n",qans[i]==INT_MAX?-1:qans[i]);
}

int main() {
	run();
	return 0;
}