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 <vector>
#include <queue>
#include <ctime>

const int Inf = 0x3f3f3f3f;
#define fp(i, a, b) for (int i = (a), I = (b) + 1; i < I; ++i)
#define fd(i, a, b) for (int i = (a), I = (b)-1; i > I; --i)
#define go(u) for (int i = head[u], v = e[i].v; i; i = e[i].nx, v = e[i].v)
inline bool cmin(int &a, int b) { return a > b ? a = b, 1 : 0; }

std::vector<int> N, S, W, E;
int Pre(std::vector<int> &A, int x) {
	if (A.empty())
		return 1;
	int l = 0, r = A.size() - 1, res = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		A[mid] <= x ? (res = mid, l = mid + 1) : r = mid - 1;
	}
	return A[res];
}
int Suf(std::vector<int> &A, int x) {
	if (A.empty())
		return 1;
	int l = 0, r = A.size() - 1, res = r;
	while (l <= r) {
		int mid = (l + r) >> 1;
		A[mid] >= x ? (res = mid, r = mid - 1) : l = mid + 1;
	}
	return A[res];
}

int head[105], tot;
struct eg {
	int v, nx, w;
	eg() {}
	eg(int v, int nx, int w) : v(v), nx(nx), w(w) {}
} e[1005];
inline void add(int u, int v, int w) { e[++tot] = eg(v, head[u], w), head[u] = tot; }

int n, m, Q, cnt, id[25][25], dis[205], vis[205];
char s[100005], t[100005];

struct node {
	int u, d;
	node() {}
	node(int uu, int dd) : u(uu), d(dd) {}
	inline bool operator<(const node &b) const { return d > b.d; }
};
std::priority_queue<node> q;

int dijk(int S, int T) {
	fp(i, 1, cnt) dis[i] = Inf, vis[i] = 0;
	q.push(node(S, 0)), dis[S] = 0;
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		go(u) if (cmin(dis[v], dis[u] + e[i].w)) q.push(node(v, dis[v]));
	}
	return dis[T] < Inf ? dis[T] : -1;
}

int main() {
//	freopen("distance.in", "r", stdin);
//	freopen("distance.out", "w", stdout);
	scanf("%d%d%d%s%s", &n, &m, &Q, s + 1, t + 1);
	fp(i, 1, n) s[i] == 'E' ? E.push_back(i) : W.push_back(i);
	fp(i, 1, m) t[i] == 'S' ? S.push_back(i) : N.push_back(i);
	while (Q--) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		std::vector<int> X, Y;
		X.push_back(Pre(E, a)), X.push_back(Pre(W, a)), X.push_back(Suf(E, a)), X.push_back(Suf(W, a));
		X.push_back(Pre(E, c)), X.push_back(Pre(W, c)), X.push_back(Suf(E, c)), X.push_back(Suf(W, c));
		Y.push_back(Pre(S, b)), Y.push_back(Pre(N, b)), Y.push_back(Suf(S, b)), Y.push_back(Suf(N, b));
		Y.push_back(Pre(S, d)), Y.push_back(Pre(N, d)), Y.push_back(Suf(S, d)), Y.push_back(Suf(N, d));
		std::sort(X.begin(), X.end()), X.resize(unique(X.begin(), X.end()) - X.begin());
		std::sort(Y.begin(), Y.end()), Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
		int lx = X.size(), ly = Y.size(), S, T;
		cnt = 0;
		fp(i, 0, lx - 1) fp(j, 0, ly - 1) {
			id[i][j] = ++cnt;
			if (X[i] == a && Y[j] == b)
				S = cnt;
			if (X[i] == c && Y[j] == d)
				T = cnt;
		}
		fp(i, 1, cnt) head[i] = 0;
		tot = 0;
		fp(i, 0, lx - 1) if (s[X[i]] == 'E') fp(j, 0, ly - 2) add(id[i][j], id[i][j + 1], Y[j + 1] - Y[j]);
		else fp(j, 1, ly - 1) add(id[i][j], id[i][j - 1], Y[j] - Y[j - 1]);
		fp(j, 0, ly - 1) if (t[Y[j]] == 'S') fp(i, 0, lx - 2) add(id[i][j], id[i + 1][j], X[i + 1] - X[i]);
		else fp(i, 1, lx - 1) add(id[i][j], id[i - 1][j], X[i] - X[i - 1]);
		printf("%d\n", dijk(S, T));
	}
//	srand(time(0));
//	if (rand() % 2) puts("Sry");
	return 0;
}

// AtCoder ExaWizards 2019 F