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;
const int MAXN = 2e5 + 5;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
namespace ShortestPath {
	const ll INF = 1e18;
	const int MAXP = 1e6;
	struct edge {int dest, len; };
	int n; ll dist[MAXP];
	vector <edge> a[MAXP];
	set <pair <ll, int> > st;
	void addedge(int x, int y, int z) {
		a[x].push_back((edge) {y, z});
	}
	void init(int x) {
		n = x; st.clear();
		for (int i = 1; i <= n; i++) {
			dist[i] = INF;
			a[i].clear();
		}
	}
	void work(int s) {
		dist[s] = 0;
		st.insert(make_pair(0, s));
		while (!st.empty()) {
			pair <ll, int> tmp = *st.begin();
			st.erase(tmp);
			for (unsigned i = 0; i < a[tmp.second].size(); i++) {
				int dest = a[tmp.second][i].dest;
				ll newlen = tmp.first + a[tmp.second][i].len;
				if (newlen < dist[dest]) {
					st.erase(make_pair(dist[dest], dest));
					dist[dest] = newlen;
					st.insert(make_pair(dist[dest], dest));
				}
			}
		}
	}
}
int n, m, q;
char h[MAXN], v[MAXN];
int hpre[MAXN][2], hsuf[MAXN][2];
int vpre[MAXN][2], vsuf[MAXN][2];
int nx, ny; vector <int> x, y;
bool sx[MAXN], sy[MAXN];
void addx(int pos) {
	if (!sx[pos]) {
		sx[pos] = true;
		x.push_back(pos);
	}
}
void addy(int pos) {
	if (!sy[pos]) {
		sy[pos] = true;
		y.push_back(pos);
	}
}
int path(pair <int, int> s, pair <int, int> t) {
	nx = x.size(), ny = y.size();
	static int point[16][16];
	int tot = 0;
	for (int i = 0; i < nx; i++)
	for (int j = 0; j < ny; j++)
		point[i][j] = ++tot;
	ShortestPath :: init(tot);
	for (int i = 0; i < nx; i++)
	for (int j = 0; j < ny; j++) {
		if (h[x[i]] == 'E' && j < ny - 1) ShortestPath :: addedge(point[i][j], point[i][j + 1], y[j + 1] - y[j]);
		if (h[x[i]] == 'W' && j > 0) ShortestPath :: addedge(point[i][j], point[i][j - 1], y[j] - y[j - 1]);
		if (v[y[j]] == 'S' && i < nx - 1) ShortestPath :: addedge(point[i][j], point[i + 1][j], x[i + 1] - x[i]);
		if (v[y[j]] == 'N' && i > 0) ShortestPath :: addedge(point[i][j], point[i - 1][j], x[i] - x[i - 1]);
	}
	for (int i = 0; i < nx; i++)
	for (int j = 0; j < ny; j++)
		if (x[i] == s.first && y[j] == s.second) ShortestPath :: work(point[i][j]);
	for (int i = 0; i < nx; i++)
	for (int j = 0; j < ny; j++)
		if (x[i] == t.first && y[j] == t.second) {
			ll tmp = ShortestPath :: dist[point[i][j]];
			if (tmp > 1e8) return -1;
			else return tmp;
		}
	assert(false);
	return -1;
}
int main() {
	read(n), read(m), read(q);
	scanf("\n%s\n%s", h + 1, v + 1);
	for (int i = 1; i <= n; i++) {
		hpre[i][0] = hpre[i - 1][0];
		hpre[i][1] = hpre[i - 1][1];
		if (h[i] == 'E') hpre[i][1] = i;
		else hpre[i][0] = i;
	}
	for (int i = n; i >= 1; i--) {
		hsuf[i][0] = hsuf[i + 1][0];
		hsuf[i][1] = hsuf[i + 1][1];
		if (h[i] == 'E') hsuf[i][1] = i;
		else hsuf[i][0] = i;
	}
	for (int i = 1; i <= m; i++) {
		vpre[i][0] = vpre[i - 1][0];
		vpre[i][1] = vpre[i - 1][1];
		if (v[i] == 'S') vpre[i][1] = i;
		else vpre[i][0] = i;
	}
	for (int i = m; i >= 1; i--) {
		vsuf[i][0] = vsuf[i + 1][0];
		vsuf[i][1] = vsuf[i + 1][1];
		if (v[i] == 'S') vsuf[i][1] = i;
		else vsuf[i][0] = i;
	}
	sx[0] = sy[0] = true;
	for (int i = 1; i <= q; i++) {
		pair <int, int> s, t;
		read(s.first), read(s.second);
		read(t.first), read(t.second);
			addy(vsuf[s.second][0]);
			addy(vsuf[s.second][1]);
			addy(vpre[s.second][0]);
			addy(vpre[s.second][1]);
			addy(vpre[t.second][0]);
			addy(vpre[t.second][1]);
			addy(vsuf[t.second][0]);
			addy(vsuf[t.second][1]);
			addx(hsuf[s.first][0]);
			addx(hsuf[s.first][1]);
			addx(hpre[s.first][0]);
			addx(hpre[s.first][1]);
			addx(hpre[t.first][0]);
			addx(hpre[t.first][1]);
			addx(hsuf[t.first][0]);
			addx(hsuf[t.first][1]);
		sort(x.begin(), x.end());
		sort(y.begin(), y.end());
		writeln(path(s, t));
		for (auto pos : x)
			sx[pos] = false;
		for (auto pos : y)
			sy[pos] = false;
		x.clear(), y.clear();
	}
	return 0;
}