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:
//Δ_F
#include<iostream>
#include<cstdio>
#include<fstream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cmath>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long LL;
typedef double DB;
const int N = 111111;
const int inf = 1e9;
int ab(int x,int y){
	if(x>y)
		return x-y;
	return y-x;
}
int n,m,q,w,a[N][2],b[N][2][2][2];
char s[N];
struct node{
	int e[2],s;
	node(int x=0,int y=0,int z=0){
		e[0]=x,e[1]=y,s=z;
	}
};
vector<node> v1,v2;
void dfs(int k,node p,int las,int rev,vector<node>&v){
	v.push_back(p);
	if(k>=2)
		return;
	int i,x;
	node q;
	for(i=0;i<2;i=i+1){
		if(las==i)
			continue;
		x=p.e[i];
		x=b[x][i][a[p.e[i^1]][i^1]^rev][a[x][i]^1];
		if(!x)
			continue;
		q=p;
		q.e[i]=x;
		q.s+=ab(x,p.e[i]);
		dfs(k+1,q,i,rev,v);
	}
}
bool ok(int i,int u,int s,int t){
	return (s==t)||((s>t)^a[u][i]);
}
void chk(node p,node q){
	int i,o=p.s+q.s+ab(p.e[0],q.e[0])+ab(p.e[1],q.e[1]);
	for(i=0;i<2;i=i+1)
		if(ok(i,p.e[i],p.e[i^1],q.e[i^1])&&ok(i^1,q.e[i^1],p.e[i],q.e[i]))
			w=min(w,o);
}
int main()
{
	int i,j,x,y;
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s",s+1);
	for(i=1;i<=n;i=i+1)
		a[i][0]=s[i]=='E';
	for(i=1;i<=n;i=i+1){
		for(j=0;j<2;j=j+1)
			b[i][0][0][j]=b[i-1][0][0][j];
		b[i][0][0][a[i][0]]=i;
	}
	for(i=n;i;i=i-1){
		for(j=0;j<2;j=j+1)
			b[i][0][1][j]=b[i+1][0][1][j];
		b[i][0][1][a[i][0]]=i;
	}
	scanf("%s",s+1);
	for(i=1;i<=m;i=i+1)
		a[i][1]=s[i]=='S';
	for(i=1;i<=m;i=i+1){
		for(j=0;j<2;j=j+1)
			b[i][1][0][j]=b[i-1][1][0][j];
		b[i][1][0][a[i][1]]=i;
	}
	for(i=m;i;i=i-1){
		for(j=0;j<2;j=j+1)
			b[i][1][1][j]=b[i+1][1][1][j];
		b[i][1][1][a[i][1]]=i;
	}
	while(q--){
		scanf("%d%d%d%d",&i,&j,&x,&y);
		v1.clear(),v2.clear();
		dfs(0,node(i,j),-1,0,v1);
		dfs(0,node(x,y),-1,1,v2);
		w=inf;
		for(i=0;i<v1.size();i=i+1)
			for(j=0;j<v2.size();j=j+1)
				chk(v1[i],v2[j]);
		if(w>=inf)
			w=-1;
		printf("%d\n",w);
	}
	return 0;
}