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 <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

int main()
{
    int n, m, q;
    cin>>n>>m>>q;
    string s, t;
    cin>>s>>t;
    vector<int> vw, ve, vn, vs;
    for(int i=0; i<n; i++){
        if(s[i]=='W') vw.push_back(i);
        else ve.push_back(i);
    }
    for(int i=0; i<m; i++){
        if(t[i]=='N') vn.push_back(i);
        else vs.push_back(i);
    }
    while(q--){
        int a, b, c, d;
        cin>>a>>b>>c>>d;
        a--; b--; c--; d--;
        int h[6], w[6];
        h[1]=min(a, c), h[4]=max(a, c), w[1]=min(b, d), w[4]=max(b, d);
        if(s[h[1]]=='W'){
            h[2]=upper_bound(ve.begin(), ve.end(), h[1])-ve.begin();
            if(h[2]-1>=0) h[0]=ve[h[2]-1];
            else h[0]=-1;
            if(h[2]<ve.size()) h[2]=ve[h[2]];
            else h[2]=-1;
            int k=upper_bound(vw.begin(), vw.end(), h[1])-vw.begin();
            if(k<vw.size()) h[3]=vw[k];
            else h[3]=-1;
            if(h[2]>=h[4]) h[2]=-1;
            if(h[3]>=h[4]) h[3]=-1;
        }else{
            h[2]=upper_bound(vw.begin(), vw.end(), h[1])-vw.begin();
            if(h[2]-1>=0) h[0]=vw[h[2]-1];
            else h[0]=-1;
            if(h[2]<vw.size()) h[2]=vw[h[2]];
            else h[2]=-1;
            int k=upper_bound(ve.begin(), ve.end(), h[1])-ve.begin();
            if(k<ve.size()) h[3]=ve[k];
            else h[3]=-1;
            if(h[2]>=h[4]) h[2]=-1;
            if(h[3]>=h[4]) h[3]=-1;
        }
        if(s[h[4]]=='W'){
            h[5]=upper_bound(ve.begin(), ve.end(), h[4])-ve.begin();
            if(h[5]<ve.size()) h[5]=ve[h[5]];
            else h[5]=-1;
        }else{
            h[5]=upper_bound(vw.begin(), vw.end(), h[4])-vw.begin();
            if(h[5]<vw.size()) h[5]=vw[h[5]];
            else h[5]=-1;
        }
        if(t[w[1]]=='N'){
            w[2]=upper_bound(vs.begin(), vs.end(), w[1])-vs.begin();
            if(w[2]-1>=0) w[0]=vs[w[2]-1];
            else w[0]=-1;
            if(w[2]<vs.size()) w[2]=vs[w[2]];
            else w[2]=-1;
            int k=upper_bound(vn.begin(), vn.end(), w[1])-vn.begin();
            if(k<vn.size()) w[3]=vn[k];
            else w[3]=-1;
            if(w[2]>=w[4]) w[2]=-1;
            if(w[3]>=w[4]) w[3]=-1;
        }else{
            w[2]=upper_bound(vn.begin(), vn.end(), w[1])-vn.begin();
            if(w[2]-1>=0) w[0]=vn[w[2]-1];
            else w[0]=-1;
            if(w[2]<vn.size()) w[2]=vn[w[2]];
            else w[2]=-1;
            int k=upper_bound(vs.begin(), vs.end(), w[1])-vs.begin();
            if(k<vs.size()) w[3]=vs[k];
            else w[3]=-1;
            if(w[2]>=w[4]) w[2]=-1;
            if(w[3]>=w[4]) w[3]=-1;
        }
        if(t[w[4]]=='N'){
            w[5]=upper_bound(vs.begin(), vs.end(), w[4])-vs.begin();
            if(w[5]<vs.size()) w[5]=vs[w[5]];
            else w[5]=-1;
        }else{
            w[5]=upper_bound(vn.begin(), vn.end(), w[4])-vn.begin();
            if(w[5]<vn.size()) w[5]=vn[w[5]];
            else w[5]=-1;
        }
        if(h[2]>h[3]) swap(h[2], h[3]);
        if(w[2]>w[3]) swap(w[2], w[3]);
        int h1[6], w1[6], cx=0, cy=0;
        for(int i=0; i<6; i++){
            if(h[i]==-1) continue;
            h1[cx++]=h[i];
        }
        for(int i=0; i<6; i++){
            if(w[i]==-1) continue;
            w1[cy++]=w[i];
        }
        int ax, ay, bx, by;
        for(int j=0; j<cx; j++){
            if(h1[j]==a) ax=j;
            if(h1[j]==c) bx=j;
        }
        for(int j=0; j<cy; j++){
            if(w1[j]==b) ay=j;
            if(w1[j]==d) by=j;
        }
        vector<P> g[36];
        for(int i=0; i<cx; i++){
            for(int j=0; j<cy-1; j++){
                if(w1[j]==w1[j+1]){
                    g[i*cy+j+1].push_back({w1[j+1]-w1[j], i*cy+j});
                    g[i*cy+j].push_back({w1[j+1]-w1[j], i*cy+j+1});
                }else if(s[h1[i]]=='W') g[i*cy+j+1].push_back({w1[j+1]-w1[j], i*cy+j});
                else g[i*cy+j].push_back({w1[j+1]-w1[j], i*cy+j+1});
            }
        }
        for(int j=0; j<cy; j++){
            for(int i=0; i<cx-1; i++){
                if(h1[i]==h1[i+1]){
                    g[(i+1)*cy+j].push_back({h1[i+1]-h1[i], i*cy+j});
                    g[i*cy+j].push_back({h1[i+1]-h1[i], (i+1)*cy+j});
                }else if(t[w1[j]]=='N') g[(i+1)*cy+j].push_back({h1[i+1]-h1[i], i*cy+j});
                else g[i*cy+j].push_back({h1[i+1]-h1[i], (i+1)*cy+j});
            }
        }
        priority_queue<P, vector<P>, greater<P>> que;
        int dist[36];
        const int INF=1e9+7;
        fill(dist, dist+36, INF);
        que.push({0, ax*cy+ay});
        dist[ax*cy+ay]=0;
        while(!que.empty()){
            P p=que.top(); que.pop();
            int x=p.second;
            if(dist[x]<p.first) continue;
            for(auto pr:g[x]){
                int y=pr.second, e=pr.first;
                if(dist[y]>dist[x]+e){
                    dist[y]=dist[x]+e;
                    que.push({dist[y], y});
                }
            }
        }
        if(dist[bx*cy+by]<INF) printf("%d\n", dist[bx*cy+by]);
        else printf("-1\n");
    }
	return 0;
}