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:
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <array>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
#include <memory>
#include <regex>
using namespace std;

const int INF = INT_MAX / 4;

int selectSmall(const set<int>& s, int a)
{
    auto it = s.upper_bound(a);
    if(it == s.begin())
        return -INF;
    -- it;
    return *it;
}

int selectLarge(const set<int>& s, int a)
{
    auto it = s.lower_bound(a);
    if(it == s.end())
        return INF;
    return *it;
}

int solve(
    const set<int>& leftRoad,
    const set<int>& rightRoad,
    const set<int>& upRoad,
    const set<int>& downRoad,
    int sy, int sx, int gy, int gx, int depth
)
{
    if(sy == gy){
        if((leftRoad.find(sy) != leftRoad.end()) ^ (sx < gx))
            return abs(sx - gx);
    }

    if(depth == 0)
        return INF;

    int ans = INF;
    if(leftRoad.find(sy) != leftRoad.end()){
        if(upRoad.find(sx) == upRoad.end()){
            int x1 = selectSmall(upRoad, sx);
            ans = min(ans, abs(sx - x1) + solve(upRoad, downRoad, leftRoad, rightRoad, x1, sy, gx, gy, depth - 1));
        }
        else{
            int x2 = selectSmall(downRoad, sx);
            ans = min(ans, abs(sx - x2) + solve(upRoad, downRoad, leftRoad, rightRoad, x2, sy, gx, gy, depth - 1));
        }
        if(gx < sx){
            int x3 = selectSmall(upRoad, gx);
            int x4 = selectSmall(downRoad, gx);
            ans = min(ans, abs(sx - x3) + solve(upRoad, downRoad, leftRoad, rightRoad, x3, sy, gx, gy, depth - 1));
            ans = min(ans, abs(sx - x4) + solve(upRoad, downRoad, leftRoad, rightRoad, x4, sy, gx, gy, depth - 1));
        }
    }
    else{
        if(upRoad.find(sx) == upRoad.end()){
            int x1 = selectLarge(upRoad, sx);
            ans = min(ans, abs(sx - x1) + solve(upRoad, downRoad, leftRoad, rightRoad, x1, sy, gx, gy, depth - 1));
        }
        else{
            int x2 = selectLarge(downRoad, sx);
            ans = min(ans, abs(sx - x2) + solve(upRoad, downRoad, leftRoad, rightRoad, x2, sy, gx, gy, depth - 1));
        }
        if(sx < gx){
            int x3 = selectLarge(upRoad, gx);
            int x4 = selectLarge(downRoad, gx);
            ans = min(ans, abs(sx - x3) + solve(upRoad, downRoad, leftRoad, rightRoad, x3, sy, gx, gy, depth - 1));
            ans = min(ans, abs(sx - x4) + solve(upRoad, downRoad, leftRoad, rightRoad, x4, sy, gx, gy, depth - 1));
        }
    }
    return ans;
}

int main()
{
    int h, w, q;
    cin >> h >> w >> q;
    string s, t;
    cin >> s >> t;

    set<int> leftRoad, rightRoad, upRoad, downRoad;
    for(int y=0; y<h; ++y){
        if(s[y] == 'W')
            leftRoad.insert(y+1);
        else
            rightRoad.insert(y+1);
    }
    for(int x=0; x<w; ++x){
        if(t[x] == 'N')
            upRoad.insert(x+1);
        else
            downRoad.insert(x+1);
    }

    while(--q >= 0){
        int sy, sx, gy, gx;
        cin >> sy >> sx >> gy >> gx;
        int ans = min(solve(leftRoad, rightRoad, upRoad, downRoad, sy, sx, gy, gx, 4),
                      solve(upRoad, downRoad, leftRoad, rightRoad, sx, sy, gx, gy, 4));
        if(ans < INF)
            cout << ans << endl;
        else
            cout << -1 << endl;
    }

    return 0;
}