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;

#define MAX 200002

int n;
int m;

char buf[MAX];
string s;
string t;

int qq;

vector<int> row[2];
vector<int> col[2];

vector<int> R;
vector<int> C;

void row_ava(int y) {
	for (int i = 0; i < 2; i++) {
		int id = lower_bound(row[i].begin(), row[i].end(), y) - row[i].begin();
		if (id != row[i].size()) {
			R.push_back(row[i][id]);
		}
		id--;
		if (id >= 0) {
			R.push_back(row[i][id]);
		}
		id++;
		if (id != row[i].size() && row[i][id] == y) {
			id++;
			if (id != row[i].size()) {
				R.push_back(row[i][id]);
			}
		}
	}
}
void col_ava(int y) {
	for (int i = 0; i < 2; i++) {
		int id = lower_bound(col[i].begin(), col[i].end(), y) - col[i].begin();
		if (id != col[i].size()) {
			C.push_back(col[i][id]);
		}
		id--;
		if (id >= 0) {
			C.push_back(col[i][id]);
		}
		id++;
		if (id != col[i].size() && col[i][id] == y) {
			id++;
			if (id != col[i].size()) {
				C.push_back(col[i][id]);
			}
		}
	}
}

int dist[20][20];
priority_queue<pair<int, pair<int, int> >, vector<pair<int, pair<int, int> > >, greater<pair<int, pair<int, int> > > > q;

int main() {
	cin >> n>>m>>qq;
	scanf("%s", buf);
	s = buf;
	scanf("%s", buf);
	t = buf;
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'W') {
			row[0].push_back(i);
		}
		else {
			row[1].push_back(i);
		}
	}
	for (int i = 0; i < t.size(); i++) {
		if (t[i] == 'N') {
			col[0].push_back(i);
		}
		else {
			col[1].push_back(i);
		}
	}
	while (qq--) {
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		a--;
		b--;
		c--;
		d--;
		R.clear();
		C.clear();
		row_ava(a);
		row_ava(c);
		col_ava(b);
		col_ava(d);
		sort(R.begin(), R.end());
		R.erase(unique(R.begin(), R.end()),R.end());
		sort(C.begin(), C.end());
		C.erase(unique(C.begin(), C.end()),C.end());
		pair<int, int> star = make_pair(-1, -1);
		pair<int, int> en = make_pair(-1, -1);
		for (int i = 0; i < R.size(); i++) {
			for (int j = 0; j < C.size(); j++) {
				dist[i][j] = -1;
				if (R[i] == a && C[j] == b) {
					star = make_pair(i, j);
				}
				if (R[i] == c && C[j] == d) {
					en = make_pair(i, j);
				}
			}
		}
		dist[star.first][star.second] = 0;
		q.push(make_pair(0,make_pair(star.first, star.second)));
		while (!q.empty()) {
			int x = q.top().second.first;
			int y = q.top().second.second;
			int est = q.top().first;
			q.pop();
			int ds = dist[x][y];
			if (ds != est)continue;
			if (s[R[x]] == 'W') {
				if (y) {
					int nex = (C[y] - C[y - 1]) + ds;
					if (dist[x][y-1]==-1||dist[x][y - 1] > nex) {
						dist[x][y - 1] = nex;
						q.push(make_pair(nex,make_pair(x, y - 1)));
						//continue;
					}
				}
			}
			if (s[R[x]] == 'E') {
				if (y+1<C.size()) {
					int nex = (C[y+1] - C[y]) + ds;
					if (dist[x][y + 1] == -1 || dist[x][y +1] > nex) {
						dist[x][y + 1] = nex;
						q.push(make_pair(nex, make_pair(x, y + 1)));
						//continue;
					}
				}
			}
			if (t[C[y]] == 'N') {
				if (x) {
					int nex = (R[x] - R[x - 1]) + ds;
					if (dist[x - 1][y] == -1 || dist[x - 1][y] > nex) {
						dist[x - 1][y] = nex;
						q.push(make_pair(nex, make_pair(x - 1, y)));
					}
				}
			}
			if (t[C[y]] == 'S') {
				if (x+1<R.size()) {
					int nex = (R[x+1] - R[x]) + ds;
					if (dist[x + 1][y] == -1 || dist[x + 1][y] > nex) {
						dist[x + 1][y] = nex;
						q.push(make_pair(nex, make_pair(x + 1, y)));
					}
				}
			}
		}
		printf("%d\n", dist[en.first][en.second]);
	}

	return 0;
}