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>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int N = 100, INF = 5e18;
vector <ii> g[N];
int dist[N];
bool in[N];

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n, m, q;
    cin >> n >> m >> q;

    string s, t;
    cin >> s >> t;

    while (q--) {

        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        --x1; --y1; --x2; --y2;

        auto add_row = [&](vector <int> &row, int x) {
            row.app(x);
            for (int i = x - 1; i >= 0; --i)
                if (s[i] != s[x]) {
                    row.app(i);
                    break;
                }   
            for (int i = x + 1; i < n; ++i)
                if (s[i] != s[x]) {
                    row.app(i);
                    break;
                }               
        };
        
        auto add_col = [&](vector <int> &col, int y) {
            col.app(y);
            for (int i = y - 1; i >= 0; --i)
                if (t[i] != t[y]) {
                    col.app(i);
                    break;
                }           
            for (int i = y + 1; i < m; ++i)
                if (t[i] != t[y]) {
                    col.app(i);
                    break;
                }           
        };

        vector <int> row;
        add_row(row, x1);
        add_row(row, x2);

        vector <int> col;
        add_col(col, y1);
        add_col(col, y2);

        auto compr = [](vector <int> &a) {
            sort(all(a));
            a.resize(unique(all(a)) - a.begin());
        };

        compr(row);
        compr(col);

        x1 = lower_bound(all(row), x1) - row.begin();
        x2 = lower_bound(all(row), x2) - row.begin();
        
        y1 = lower_bound(all(col), y1) - col.begin();
        y2 = lower_bound(all(col), y2) - col.begin();

        int S = x1 * 10 + y1;
        int T = x2 * 10 + y2;

    //E - right
    //W - left
    //N - up
    //S - down

        for (int i = 0; i < N; ++i)
            g[i].clear();            

        for (int i = 0; i < row.size(); ++i) {
            for (int j = 0; j < col.size(); ++j) {
                int u = i * 10 + j;
                if (s[row[i]] == 'E') {
                    if (j + 1 < col.size()) {
                        //cout << u << ' ' << u + 1 << ' ' << col[j+1]-col[j] << endl;
                        g[u].app(mp(u+1, col[j+1]-col[j]));                        
                    }   
                }   
                else {
                    if (j) {
                        //cout << u << ' ' << u - 1 << ' ' << col[j]-col[j-1] << endl;
                        g[u].app(mp(u-1, col[j]-col[j-1]));
                    }   
                }

                if (t[col[j]] == 'N') {
                    if (i) {
                        g[u].app(mp(u-10, row[i]-row[i-1]));
                    }   
                }   
                else {
                    if (i+1 < row.size()) {
                        g[u].app(mp(u+10, row[i+1]-row[i]));
                    }   
                }   
            }   
        }   

        for (int i = 0; i < N; ++i)
            dist[i] = INF;        

        dist[S] = 0;
        queue <int> q;
        q.push(S);
        in[S] = 1;

        /*
        for (auto e : row)
            cout << e << ' ';
        cout << endl;

        for (auto e : col)
            cout << e << ' ';
        cout << endl;
        */

        while (q.size()) {
            int u = q.front();
            in[u] = 0; q.pop();

            //cout << u << ' ' << dist[u] << endl;

            for (auto e : g[u]) {
                int v = e.f, c = e.s;
                if (dist[u]+c < dist[v]) {
                    dist[v] = dist[u]+c;
                    if (!in[v]) {
                        in[v] = 1;
                        q.push(v);
                    }   
                }   
            }
        }

        //cout << "T " << T << endl;

        if (dist[T] == INF)
            cout << -1 << endl;
        else
            cout << dist[T] << endl;
    }   
}