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 <set>
#include <queue>
#include <algorithm>

typedef std::set<int>::iterator Iter;
const int Inf = 0x3f3f3f3f;
const int MN = 100005;

int N, M, Q;
char Str1[MN], Str2[MN];
std::set<int> se, sw, ss, sn;

int dx[10], dy[10], cx, cy;
inline void Add(std::set<int> &st, int id, int *dw, int &cw) {
	if (st.empty()) return ;
	Iter It = st.lower_bound(id);
	if (It != st.end()) dw[++cw] = *It;
	if (It != st.begin()) --It, dw[++cw] = *It;
}

int Id[10][10], Cnt, S, T;
int h[40], nxt[65], to[65], w[65], tot;
inline void Ins(int x, int y, int z) { nxt[++tot] = h[x], to[tot] = y, w[tot] = z, h[x] = tot; }

struct nde {
	int d, u;
	nde() {}
	nde(int d, int u) : d(d), u(u) {}
	inline friend bool operator <(nde i, nde j) {
		return i.d == j.d ? i.u < j.u : i.d > j.d;
	}
};

std::priority_queue<nde> pq;
int Vis[40], Dis[40];
inline int Dijkstra() {
	for (int i = 1; i <= Cnt; ++i) Vis[i] = 0, Dis[i] = Inf;
	Dis[S] = 0, pq.push(nde(0, S));
	while (!pq.empty()) {
		nde p = pq.top(); pq.pop();
		int d = p.d, u = p.u;
		if (Vis[u]) continue;
		Vis[u] = 1;
		for (int i = h[u]; i; i = nxt[i])
			if (Dis[to[i]] > d + w[i])
				Dis[to[i]] = d + w[i],
				pq.push(nde(Dis[to[i]], to[i]));
	}
	return Dis[T] == Inf ? -1 : Dis[T];
}

int main() {
	scanf("%d%d%d", &N, &M, &Q);
	scanf("%s%s", Str1 + 1, Str2 + 1);
	for (int i = 1; i <= N; ++i) (Str1[i] == 'E' ? se : sw).insert(i);
	for (int i = 1; i <= M; ++i) (Str2[i] == 'S' ? ss : sn).insert(i);
	while (Q--) {
		int sx, sy, tx, ty;
		scanf("%d%d%d%d", &sx, &sy, &tx, &ty);
		dx[1] = sx, dx[2] = tx;
		dy[1] = sy, dy[2] = ty;
		cx = cy = 2;
		Add(Str1[sx] == 'E' ? sw : se, sx, dx, cx);
		Add(Str1[tx] == 'E' ? sw : se, tx, dx, cx);
		Add(Str2[sy] == 'S' ? sn : ss, sy, dy, cy);
		Add(Str2[ty] == 'S' ? sn : ss, ty, dy, cy);
		std::sort(dx + 1, dx + cx + 1);
		cx = std::unique(dx + 1, dx + cx + 1) - dx - 1;
		std::sort(dy + 1, dy + cy + 1);
		cy = std::unique(dy + 1, dy + cy + 1) - dy - 1;
		Cnt = tot = 0;
		for (int i = 1; i <= cx; ++i)
			for (int j = 1; j <= cy; ++j) {
				Id[i][j] = ++Cnt;
				if (dx[i] == sx && dy[j] == sy) S = Cnt;
				if (dx[i] == tx && dy[j] == ty) T = Cnt;
			}
		for (int i = 1; i <= Cnt; ++i) h[i] = 0;
		for (int i = 1; i <= cx; ++i) {
			int dir = Str1[dx[i]] == 'E';
			for (int j = 1; j < cy; ++j)
				Ins(Id[i][j + !dir], Id[i][j + dir], dy[j + 1] - dy[j]);
		}
		for (int j = 1; j <= cy; ++j) {
			int dir = Str2[dy[j]] == 'S';
			for (int i = 1; i < cx; ++i)
				Ins(Id[i + !dir][j], Id[i + dir][j], dx[i + 1] - dx[i]);
		}
		printf("%d\n", Dijkstra());
	}
	return 0;
}

// Source : AtCoder ExaWizards 2019 F