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>
#define inf 0x3f3f3f3f
using namespace std;
const int N=1e5+5;
int n,m,q,tot,id[7][7],dis[50][50];
vector<int>north,south,east,west;
char s1[N],s2[N];
unordered_map<int,int>vis1,vis2;
vector<int>v1,v2;
void solve2(int a,int b)
{
    int pos;
    if(s2[b]=='N')
    {
        pos=lower_bound(south.begin(),south.end(),b)-south.begin();
        if(pos<south.size()&&!vis2[south[pos]])
        {
            v2.push_back(south[pos]);
            vis2[south[pos]]=true;
        }
    }
    else
    {
        pos=lower_bound(north.begin(),north.end(),b)-north.begin();
        if(pos<north.size()&&!vis2[north[pos]])
        {
            v2.push_back(north[pos]);
            vis2[north[pos]]=true;
        }
    }
    if(s2[b]=='N')
    {
        pos=lower_bound(south.begin(),south.end(),b)-south.begin()-1;
        if(pos<south.size()&&!vis2[south[pos]])
        {
            v2.push_back(south[pos]);
            vis2[south[pos]]=true;
        }
    }
    else
    {
        pos=lower_bound(north.begin(),north.end(),b)-north.begin()-1;
        if(pos<north.size()&&!vis2[north[pos]])
        {
            v2.push_back(north[pos]);
            vis2[north[pos]]=true;
        }
    }
}
void solve1(int a,int b)
{
    int pos;
    if(s1[a]=='W')
    {
        pos=lower_bound(east.begin(),east.end(),a)-east.begin();
        if(pos<east.size()&&!vis1[east[pos]])
        {
            v1.push_back(east[pos]);
            vis1[east[pos]]=true;
        }
    }
    else
    {
        pos=lower_bound(west.begin(),west.end(),a)-west.begin();
        if(pos<west.size()&&!vis1[west[pos]])
        {
            v1.push_back(west[pos]);
            vis1[west[pos]]=true;
        }
    }
    if(s1[a]=='W')
    {
        pos=lower_bound(east.begin(),east.end(),a)-east.begin()-1;
        if(pos>=0&&!vis1[east[pos]])
        {
            v1.push_back(east[pos]);
            vis1[east[pos]]=true;
        }
    }
    else
    {
        pos=lower_bound(west.begin(),west.end(),a)-west.begin()-1;
        if(pos>=0&&!vis1[west[pos]])
        {
            v1.push_back(west[pos]);
            vis1[west[pos]]=true;
        }
    }
}
struct node
{
    int u,x;
    node(int u=0,int x=0):u(u),x(x){}
    bool operator<(const node&o)const
    {
        return x>o.x;
    }
};
int d[50*50];
bool vis[50*50];
int dijkstra(int s,int t)
{
    memset(d,inf,sizeof(d));
    memset(vis,false,sizeof(vis));
    priority_queue<node>q;
    d[s]=0;
    q.push(node(s,0));
    while(!q.empty())
    {
        int u=q.top().u;q.pop();
        if(vis[u]) continue;
        if(u==t) return d[t];
        vis[u]=true;
        for(int i=1;i<=tot;i++)
            if(d[i]>d[u]+dis[u][i])
        {
            d[i]=d[u]+dis[u][i];
            q.push(node(i,d[i]));
        }
    }
    return d[t];
}
void ts(int x)
{
    //cout<<"test "<<x<<endl;
}
int main()
{
    scanf("%d%d%d",&n,&m,&q);
    scanf("%s",s1+1);
    for(int i=1;i<=n;i++)
        if(s1[i]=='E')
        east.push_back(i);
    else west.push_back(i);
    scanf("%s",s2+1);
    for(int i=1;i<=m;i++)
        if(s2[i]=='N') north.push_back(i);
    else south.push_back(i);
    while(q--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        vis1.clear();vis2.clear();
        v1.clear();v2.clear();
        v1.push_back(a);v2.push_back(b);
        vis1[a]=vis2[b]=true;
        if(!vis1[c]) v1.push_back(c),vis1[c]=true;
        if(!vis2[d]) v2.push_back(d),vis2[d]=true;
        solve1(a,b);solve1(c,d);
        solve2(a,b);solve2(c,d);
        sort(v1.begin(),v1.end());
        sort(v2.begin(),v2.end());
        memset(dis,inf,sizeof(dis));
        memset(id,0,sizeof(id));
        tot=0;
        int s,t;
        for(int i=0;i<v1.size();i++)
            for(int j=0;j<v2.size();j++)
        {
            //cout<<tot+1<<' '<<v1[i]<<' '<<v2[j]<<endl;
            id[i][j]=++tot;
            if(v1[i]==a&&v2[j]==b) s=tot;
            if(v1[i]==c&&v2[j]==d) t=tot;
            if(j>0)
            {
                if(s1[v1[i]]=='W')
                    dis[id[i][j]][id[i][j-1]]=v2[j]-v2[j-1];
                else dis[id[i][j-1]][id[i][j]]=v2[j]-v2[j-1];
            }
            if(i>0)
            {
                if(s2[v2[j]]=='N')
                    dis[id[i][j]][id[i-1][j]]=v1[i]-v1[i-1];
                else dis[id[i-1][j]][id[i][j]]=v1[i]-v1[i-1];
            }
        }
        //cout<<tot<<endl;
        for(int i=1;i<=tot;i++) dis[i][i]=0;
        //cout<<s<<' '<<t<<endl;
        //for(int i=1;i<=tot;i++)
       //     for(int j=1;j<=tot;j++)
        //        printf(j==tot?"%d\n":"%d\t",dis[i][j]==inf?-1:dis[i][j]);
        int dis=dijkstra(s,t);
        if(dis==inf) printf("-1\n");
        else printf("%d\n",dis);
    }
}