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;
int main() {
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n, m, q;
  string S, T;
  cin >> n >> m >> q >> S >> T;
  auto init_pre = [&] (string str, vector<int> &pre_0, vector<int> &pre_1) {
    for (int i = 0; i < str.size(); i++) {
      if (!i) {
        pre_0[i] = -1;
        pre_1[i] = -1;
      } else {
        pre_0[i] = pre_0[i - 1];
        pre_1[i] = pre_1[i - 1];
      }
      if (str[i] == 'W' || str[i] == 'N') {
        pre_0[i] = i;
      } else {
        pre_1[i] = i;
      }
    }
  };
  vector<int> pre_W(n), pre_E(n), pre_N(m), pre_S(m);
  init_pre(S, pre_W, pre_E);
  init_pre(T, pre_N, pre_S);
  auto init_nxt = [&] (string str, vector<int> &nxt_0, vector<int> &nxt_1) {
    for (int i = str.size() - 1; i >= 0; i--) {
      if (i == str.size() - 1) {
        nxt_0[i] = str.size();
        nxt_1[i] = str.size();
      } else {
        nxt_0[i] = nxt_0[i + 1];
        nxt_1[i] = nxt_1[i + 1];
      }
      if (str[i] == 'W' || str[i] == 'N') {
        nxt_0[i] = i;
      } else {
        nxt_1[i] = i;
      }
    }
  };
  vector<int> nxt_W(n), nxt_E(n), nxt_N(m), nxt_S(m);
  init_nxt(S, nxt_W, nxt_E);
  init_nxt(T, nxt_N, nxt_S);
  vector<bool> vis_x(n), vis_y(m);
  while (q--) {
    std::vector<int> vec_x, vec_y;
    auto add_x = [&] (int x) {
      if (x >= 0 && x < n && !vis_x[x]) {
        vis_x[x] = true;
        vec_x.push_back(x);
      }
    };
    auto add_point_x = [&] (int x) {
      add_x(pre_W[x]);
      add_x(pre_E[x]);
      add_x(nxt_W[x]);
      add_x(nxt_E[x]);
    };
    auto add_y = [&] (int y) {
      if (y >= 0 && y < m && !vis_y[y]) {
        vis_y[y] = true;
        vec_y.push_back(y);
      }
    };
    auto add_point_y = [&] (int y) {
      add_y(pre_N[y]);
      add_y(pre_S[y]);
      add_y(nxt_N[y]);
      add_y(nxt_S[y]);
    };
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    add_point_x(--sx);
    add_point_x(--tx);
    add_point_y(--sy);
    add_point_y(--ty);
    sort(vec_x.begin(), vec_x.end());
    sort(vec_y.begin(), vec_y.end());
    int len_x = vec_x.size(), len_y = vec_y.size(), tot = 0;
    vector<vector<int> > node(len_x, vector<int>(len_y));
    for (int i = 0; i < len_x; i++) {
      for (int j = 0; j < len_y; j++) {
        node[i][j] = tot++;
      }
    }
    vector<vector<pair<int, int> > > adj(tot);
    for (int i = 0; i < len_x; i++) {
      for (int j = 0; j < len_y; j++) {
        if (S[vec_x[i]] == 'E' && j + 1 < len_y) {
          adj[node[i][j]].emplace_back(node[i][j + 1], vec_y[j + 1] - vec_y[j]);
        }
        if (S[vec_x[i]] == 'W' && j) {
          adj[node[i][j]].emplace_back(node[i][j - 1], vec_y[j] - vec_y[j - 1]);
        }
        if (T[vec_y[j]] == 'N' && i) {
          adj[node[i][j]].emplace_back(node[i - 1][j], vec_x[i] - vec_x[i - 1]);
        }
        if (T[vec_y[j]] == 'S' && i + 1 < len_x) {
          adj[node[i][j]].emplace_back(node[i + 1][j], vec_x[i + 1] - vec_x[i]);
        }
      }
    }
    vector<int> dis(tot, INT_MAX);
    priority_queue<pair<int, int> > que;
    int source = node[lower_bound(vec_x.begin(), vec_x.end(), sx) - vec_x.begin()][lower_bound(vec_y.begin(), vec_y.end(), sy) - vec_y.begin()];
    dis[source] = 0;
    que.emplace(0, source);
    while (!que.empty()) {
      auto it = que.top();
      que.pop();
      int u = it.second;
      if (dis[u] != -it.first) {
        continue;
      }
      for (auto e : adj[u]) {
        int v = e.first, w = e.second;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          que.emplace(-dis[v], v);
        }
      }
    }
    int end = node[lower_bound(vec_x.begin(), vec_x.end(), tx) - vec_x.begin()][lower_bound(vec_y.begin(), vec_y.end(), ty) - vec_y.begin()];
    if (dis[end] == INT_MAX) {
      cout << -1 << "\n";
    } else {
      cout << dis[end] << "\n";
    }
    for (int x : vec_x) {
      vis_x[x] = false;
    }
    for (int y : vec_y) {
      vis_y[y] = false;
    }
  }
  return 0;
}