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:
#ifdef DBG1
  #define LOCAL
#endif

#ifdef LOCAL
  #define _GLIBCXX_DEBUG
#endif

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

#ifdef DBG1
    #define dbg(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dbg(...)
#endif

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;

const int INF = int(1e29);

vector<int> buildNext(int n, const char *s) {
  vector<int> next(n, n);
  for (int i = n - 2; i >= 0; --i) {
    if (s[i] == s[i + 1]) {
      next[i] = next[i + 1];
    } else {
      next[i] = i + 1;
    }
  }
  for (int i : next) {
    dbg("%d ", i);
  }
  dbg("\n");
  return next;
}

vector<int> buildPrev(int n, const char *s) {
  vector<int> prev(n, -1);
  for (int i = 1; i < n; ++i) {
    if (s[i] == s[i - 1]) {
      prev[i] = prev[i - 1];
    } else {
      prev[i] = i - 1;
    }
  }
  for (int i : prev) {
    dbg("%d ", i);
  }
  dbg("\n");
  return prev;
}

bool solve() {
  int n, m, q;
  if (scanf("%d%d%d", &n, &m, &q) != 3) { return false; }

  static char S[101000];
  static char T[101000];
  scanf("%s%s", S, T);

  vector<int> next1 = buildNext(n, S);
  vector<int> prev1 = buildPrev(n, S);
  vector<int> next2 = buildNext(m, T);
  vector<int> prev2 = buildPrev(m, T);

  dbg("q = %d\n", q);

  for (int ii = 0; ii < q; ++ii) {
    int x1, y1, x2, y2;
    scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
    --x1, --y1, --x2, --y2;

    dbg("x1 %d y1 %d x2 %d y2 %d\n", x1, y1, x2, y2);

    vector<int> xx;
    xx.push_back(x1);
    if (next1[x1] < n) xx.push_back(next1[x1]);
    if (prev1[x1] >= 0) xx.push_back(prev1[x1]);
    xx.push_back(x2);
    if (next1[x2] < n) xx.push_back(next1[x2]);
    if (prev1[x2] >= 0) xx.push_back(prev1[x2]);
    
    vector<int> yy;
    yy.push_back(y1);
    if (next2[y1] < m) yy.push_back(next2[y1]);
    if (prev2[y1] >= 0) yy.push_back(prev2[y1]);
    yy.push_back(y2);
    if (next2[y2] < m) yy.push_back(next2[y2]);
    if (prev2[y2] >= 0) yy.push_back(prev2[y2]);

    sort(xx.begin(), xx.end());
    xx.erase(unique(xx.begin(), xx.end()), xx.end());
    sort(yy.begin(), yy.end());
    yy.erase(unique(yy.begin(), yy.end()), yy.end());

    for (int x : xx) {
      dbg("%d ", x);
    }
    dbg("\n");
    for (int y : yy) {
      dbg("%d ", y);
    }
    dbg("\n");

    vector<vector<int>> d(xx.size(), vector<int>(yy.size(), INF));
    vector<vector<bool>> used(xx.size(), vector<bool>(yy.size(), false));
    for (int i = 0; i < int(xx.size()); ++i) {
      if (xx[i] != x1) { continue; }
      for (int j = 0; j < int(yy.size()); ++j) {
        if (yy[j] == y1) {
          d[i][j] = 0;
          //dbg("start %d %d\n", i, j);
        }
      }
    }

    while (1) {
      int bestI = -1, bestJ = -1, bestD = INF;
      for (int i = 0; i < int(xx.size()); ++i) {
        for (int j = 0; j < int(yy.size()); ++j) {
          if (used[i][j] || d[i][j] == INF) { continue; }
          if (bestD > d[i][j]) {
            bestI = i, bestJ = j, bestD = d[i][j];
          }
        }
      }
      if (bestD == INF) { break; }
      
      {
        int i = bestI;
        int j = bestJ;
        //dbg("d[%d][%d] = %d\n", xx[i], yy[j], d[i][j]);
        used[i][j] = true;
        for (int i2 = 0; i2 < int(xx.size()); ++i2) {
          if ((T[yy[j]] == 'N') != (i2 < i)) { continue; }
          if (used[i2][j]) { continue; }
          //dbg("%d %d -> %d %d\n", xx[i], yy[j], xx[i2], yy[j]);
          d[i2][j] = min(d[i2][j], d[i][j] + abs(xx[i] - xx[i2]));
        }
        for (int j2 = 0; j2 < int(yy.size()); ++j2) {
          if ((S[xx[i]] == 'W') != (j2 < j)) { continue; }
          if (used[i][j2]) { continue; }
          //dbg("%d %d -> %d %d\n", xx[i], yy[j], xx[i], yy[j2]);
          d[i][j2] = min(d[i][j2], d[i][j] + abs(yy[j] - yy[j2]));
        }
      }
    }

    bool found = false;
    for (int i = 0; i < int(xx.size()); ++i) {
      if (xx[i] != x2) { continue; }
      for (int j = 0; j < int(yy.size()); ++j) {
        if (yy[j] == y2) {
          printf("%d\n", d[i][j] == INF ? -1 : d[i][j]);
          assert(!found);
          found = true;
        }
      }
    }
    assert(found);

  }

  return true;
}

int main() {
  while (solve());
  return 0;
}