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<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
using namespace std;
const int N=200005;
struct node
{
	int h,d;
}tp;
bool operator <(node a,node b)
{
	return a.d>b.d;
}
priority_queue<node> Q;
int n,m,q,lste[N],nxte[N],lstw[N],nxtw[N],lstn[N],nxtn[N],lsts[N],nxts[N],p1[N],p2[N],cnt1,cnt2,px[N],py[N],num,wx[N],wy[N],dis[N],head[N],adj[N],nxt[N],len[N],i,j,k,l,x[2],y[2];
bool v[N];
char s[N],t[N];
int Abs(int a)
{
	return a>0?a:-a;
}
void addedge(int u,int v,int w)
{
	adj[++l]=v;
	nxt[l]=head[u];
	head[u]=l;
	len[l]=w;
}
int main()
{
	scanf("%d%d%d",&n,&m,&q);
	scanf("%s%s",s+1,t+1);
	for(i=1;i<=n;++i)
		if(s[i]=='E')
		{
			lste[i]=i;
			lstw[i]=lstw[i-1];
		}
		else
		{
			lste[i]=lste[i-1];
			lstw[i]=i;
		}
	for(i=n;i>=1;--i)
		if(s[i]=='E')
		{
			nxte[i]=i;
			nxtw[i]=nxtw[i+1];
		}
		else
		{
			nxte[i]=nxte[i+1];
			nxtw[i]=i;
		}
	for(i=1;i<=m;++i)
		if(t[i]=='N')
		{
			lstn[i]=i;
			lsts[i]=lsts[i-1];
		}
		else
		{
			lstn[i]=lstn[i-1];
			lsts[i]=i;
		}
	for(i=m;i>=1;--i)
		if(t[i]=='N')
		{
			nxtn[i]=i;
			nxts[i]=nxts[i+1];
		}
		else
		{
			nxtn[i]=nxtn[i+1];
			nxts[i]=i;
		}
	while(q--)
	{
		scanf("%d%d%d%d",&x[0],&y[0],&x[1],&y[1]);
		cnt1=cnt2=0;
		for(j=0;j<=1;++j)
		{
			if(lste[x[j]])
				p1[++cnt1]=lste[x[j]];
			if(lstw[x[j]])
				p1[++cnt1]=lstw[x[j]];
			if(nxte[x[j]])
				p1[++cnt1]=nxte[x[j]];
			if(nxtw[x[j]])
				p1[++cnt1]=nxtw[x[j]];
			if(lstn[y[j]])
				p2[++cnt2]=lstn[y[j]];
			if(lsts[y[j]])
				p2[++cnt2]=lsts[y[j]];
			if(nxtn[y[j]])
				p2[++cnt2]=nxtn[y[j]];
			if(nxts[y[j]])
				p2[++cnt2]=nxts[y[j]];
		}
		num=0;
		for(i=1;i<=cnt1;++i)
			for(j=1;j<=cnt2;++j)
			{
				++num;
				wx[num]=p1[i],wy[num]=p2[j];
			}
		for(i=1;i<=num;++i)
			head[i]=0;
		l=0;
		for(i=1;i<=num;++i)
			for(j=i+1;j<=num;++j)
				if(wx[i]==wx[j])
				{
					if((wy[i]<wy[j])==(s[wx[i]]=='E'))
						addedge(i,j,Abs(wy[i]-wy[j]));
					else
						addedge(j,i,Abs(wy[i]-wy[j]));
				}
				else if(wy[i]==wy[j])
				{
					if((wx[i]<wx[j])==(t[wy[i]]=='S'))
						addedge(i,j,Abs(wx[i]-wx[j]));
					else
						addedge(j,i,Abs(wx[i]-wx[j]));
				}
		for(i=1;i<=num;++i)
			if(wx[i]==x[0]&&wy[i]==y[0])
				break;
		for(j=1;j<=num;++j)
			dis[j]=1<<30,v[j]=false;
		dis[i]=0;
		Q.push((node){i,0});
		while(!Q.empty())
		{
			tp=Q.top();
			Q.pop();
			for(j=head[tp.h];j;j=nxt[j])
				if(tp.d+len[j]<dis[adj[j]])
				{
					dis[adj[j]]=tp.d+len[j];
					Q.push((node){adj[j],dis[adj[j]]});
				}
		}
		for(i=1;i<=num;++i)
			if(wx[i]==x[1]&&wy[i]==y[1])
			{
				printf("%d\n",dis[i]<(1<<30)?dis[i]:-1);
				break;
			}
	}
	return 0;
}