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 <algorithm>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <memory>
#include <thread>
#include <tuple>

using namespace std;

char hroad[1048576]; // 가로
char vroad[1048576]; // 세로

struct seg {
  int r, c; // start
  int d; // direction
  seg() : r(0), c(0), d(0) {}
  seg(int r, int c, int d) : r(r), c(c), d(d) { }
  seg flip_x() const {
    seg s;
    s.r = r;
    s.c = -c;
    s.d = ((d <= 1) ? (1 ^ d) : d);
    return s;
  }
  seg swap_xy() const {
    seg s;
    s.r = c;
    s.c = r;
    s.d = d ^ 2;
    return s;
  }
};

const int dir[4][2] = {
  0, -1, // W
  0, 1, // E
  -1, 0, // N
  1, 0 // S
};

int check_cross(int base, seg s, seg t) {
  if (s.d == 0) {
    if (t.d == 0) return (s.r == t.r) ? (base + abs(s.c - t.c)) : -1;
    else if (t.d == 1) return (s.r == t.r && s.c >= t.c) ? (base + abs(s.c - t.c)) : -1;
    else if (t.d == 2) return (s.r <= t.r && s.c >= t.c) ? (base + abs(s.c - t.c) + abs(s.r - t.r)) : -1;
    else if (t.d == 3) return (s.r >= t.r && s.c >= t.c) ? (base + abs(s.c - t.c) + abs(s.r - t.r)) : -1;
  }
  else if (s.d == 1) {
    return check_cross(base, s.flip_x(), t.flip_x());
  }
  else if (s.d == 2) {
    return check_cross(base, s.swap_xy(), t.swap_xy());
  }
  else if (s.d == 3) {
    return check_cross(base, s.swap_xy(), t.swap_xy());
  }
}

int c2d(char v) {
  if (v == 'W') return 0;
  if (v == 'E') return 1;
  if (v == 'N') return 2;
  if (v == 'S') return 3;
  return 0;
}

int lastW[100002];
int lastE[100002];
int lastN[100002];
int lastS[100002];

int firstW[100002];
int firstE[100002];
int firstN[100002];
int firstS[100002];

void expand(seg v, vector<seg> &app) {
  if (v.d == 0) {
    if (lastN[v.c] != -1) app.emplace_back(v.r, lastN[v.c], c2d('N'));
    if (lastS[v.c] != -1) app.emplace_back(v.r, lastS[v.c], c2d('S'));
  }
  else if (v.d == 1) {
    if (firstN[v.c] != -1) app.emplace_back(v.r, firstN[v.c], c2d('N'));
    if (firstS[v.c] != -1) app.emplace_back(v.r, firstS[v.c], c2d('S'));
  }
  else if (v.d == 2) {
    if (lastW[v.r] != -1) app.emplace_back(lastW[v.r], v.c, c2d('W'));
    if (lastE[v.r] != -1) app.emplace_back(lastE[v.r], v.c, c2d('E'));
  }
  else if (v.d == 3) {
    if (firstW[v.r] != -1) app.emplace_back(firstW[v.r], v.c, c2d('W'));
    if (firstE[v.r] != -1) app.emplace_back(firstE[v.r], v.c, c2d('E'));
  }
}

int main() {
  int n, m, q;
  scanf("%d%d%d", &n, &m, &q);
  scanf("%s", hroad);
  scanf("%s", vroad);
  {
    int iW = -1, iE = -1;
    for (int i = 0; i < n; i++) {
      if (hroad[i] == 'W') {
        iW = i;
      }
      else {
        iE = i;
      }
      lastW[i] = iW;
      lastE[i] = iE;
    }
  }
  {
    int iN = -1, iS = -1;
    for (int i = 0; i < m; i++) {
      if (vroad[i] == 'N') {
        iN = i;
      }
      else {
        iS = i;
      }
      lastN[i] = iN;
      lastS[i] = iS;
    }
  }
  {
    int iW = -1, iE = -1;
    for (int i = n-1; i >= 0; i--) {
      if (hroad[i] == 'W') {
        iW = i;
      }
      else {
        iE = i;
      }
      firstW[i] = iW;
      firstE[i] = iE;
    }
  }
  {
    int iN = -1, iS = -1;
    for (int i = m-1; i >= 0; i--) {
      if (vroad[i] == 'N') {
        iN = i;
      }
      else {
        iS = i;
      }
      firstN[i] = iN;
      firstS[i] = iS;
    }
  }

  for (int i = 0; i < q; i++) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a,&b,&c,&d);
    a--, b--, c--, d--;
    int ans = -1;
    vector<seg> c1;
    vector<seg> c2;

    c1.emplace_back(a, b, c2d(hroad[a]));
    c1.emplace_back(a, b, c2d(vroad[b]));
    for (int i = 0; i < 2; i++) {
      expand(c1[i], c1);
    }
    for (int i = 2, iEnd = c1.size(); i < iEnd; i++) {
      expand(c1[i], c1);
    }

    c2.emplace_back(c, d, 1^c2d(hroad[c]));
    if (hroad[c] != 'W') {
      if (lastN[d] != -1) c2.emplace_back(c, lastN[d], 1^c2d('N'));
      if (lastS[d] != -1) c2.emplace_back(c, lastS[d], 1^c2d('S'));
    }
    else {
      if (firstN[d] != -1) c2.emplace_back(c, firstN[d], 1^c2d('N'));
      if (firstS[d] != -1) c2.emplace_back(c, firstS[d], 1^c2d('S'));
    }
    c2.emplace_back(c, d, 1^c2d(vroad[d]));
    if (vroad[d] != 'N') {
      if (lastE[c] != -1) c2.emplace_back(lastE[c], d, 1^c2d('E'));
      if (lastW[c] != -1) c2.emplace_back(lastW[c], d, 1^c2d('W'));
    }
    else {
      if (firstE[c] != -1) c2.emplace_back(firstE[c], d, 1^c2d('E'));
      if (firstW[c] != -1) c2.emplace_back(firstW[c], d, 1^c2d('W'));
    }

    for (const auto &A : c1) {
      for (const auto &B : c2) {
        int base = abs(a - A.r) + abs(b - A.c) + abs(c - B.r) + abs(d - B.c);
        int result = check_cross(base, A, B);
        if (result < 0) continue;
        if (ans == -1 || ans > result) {
          ans = result;
        }
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}