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 inf (int)(1e9)

struct edge{
	int to;
	int cost;

	edge(int to, int cost) : to(to), cost(cost){}
};

vector<int> dijkstra(vector<vector<edge> > g, int s){
	vector<int> ans(g.size(), inf);
	priority_queue<pair<int, int> > q;//(距離, 頂点番号)
	q.push(pair<int, int>(0, s));
	while(q.size() > 0){
		int dis = q.top().first, v = q.top().second;
		q.pop();
		if(dis < ans[v]){
			ans[v] = dis;
			for(int i = 0; i < g[v].size(); i++){
				q.push(pair<int, int>(dis + g[v][i].cost, g[v][i].to));
			}
		}
	}
	return ans;
}

int align(int x, int y){
	return 5 * x + y;
}

int main(){
	int N, M, Q, i, j;
	scanf("%d%d%d", &N, &M, &Q);
	vector<char> S(N + 2);
	vector<int> nextW(N + 2), nextE(N + 2), prevW(N + 2), prevE(N + 2);
	scanf("%s", &S[1]);
	nextW[N + 1] = N + 1;
	nextE[N + 1] = N + 1;
	for(i = N; i > 0; i--){
		if(S[i] == 'W'){
			nextW[i] = i;
			nextE[i] = nextE[i + 1];
		}
		else{
			nextW[i] = nextW[i + 1];
			nextE[i] = i;
		}
	}
	prevW[0] = 0;
	prevE[0] = 0;
	for(i = 1; i <= N; i++){
		if(S[i] == 'W'){
			prevW[i] = i;
			prevE[i] = prevE[i - 1];
		}
		else{
			prevW[i] = prevW[i - 1];
			prevE[i] = i;
		}
	}

	vector<char> T(M + 2);
	vector<int> nextN(M + 2), nextS(M + 2), prevN(M + 2), prevS(M + 2);
	scanf("%s", &T[1]);
	nextN[M + 1] = M + 1;
	nextS[M + 1] = M + 1;
	for(i = M; i > 0; i--){
		if(T[i] == 'N'){
			nextN[i] = i;
			nextS[i] = nextS[i + 1];
		}
		else{
			nextN[i] = nextN[i + 1];
			nextS[i] = i;
		}
	}
	prevN[0] = 0;
	prevS[0] = 0;
	for(i = 1; i <= M; i++){
		if(T[i] == 'N'){
			prevN[i] = i;
			prevS[i] = prevS[i - 1];
		}
		else{
			prevN[i] = prevN[i - 1];
			prevS[i] = i;
		}
	}
	for(int q = 0; q < Q; q++){
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		int x[5], y[5];
		x[1] = min(a, c);
		x[3] = max(a, c);
		y[1] = min(b, d);
		y[3] = max(b, d);

		if(S[x[1]] == 'W'){
			x[0] = prevE[x[1] - 1];
			x[2] = min(x[3], nextE[x[1] + 1]);
		}
		else{
			x[0] = prevW[x[1] - 1];
			x[2] = min(x[3], nextW[x[1] + 1]);
		}
		if(x[0] == 0){
			x[0] = x[1];
		}
		if(S[x[3]] == 'W'){
			x[4] = nextE[x[3] + 1];
		}
		else{
			x[4] = nextW[x[3] + 1];
		}
		if(x[4] == N + 1){
			x[4] = x[3];
		}

		if(T[y[1]] == 'N'){
			y[0] = prevS[y[1] - 1];
			y[2] = min(y[3], nextS[y[1] + 1]);
		}
		else{
			y[0] = prevN[y[1] - 1];
			y[2] = min(y[3], nextN[y[1] + 1]);
		}
		if(y[0] == 0){
			y[0] = y[1];
		}
		if(T[y[3]] == 'N'){
			y[4] = nextS[y[3] + 1];
		}
		else{
			y[4] = nextN[y[3] + 1];
		}
		if(y[4] == M + 1){
			y[4] = y[3];
		}

/*		printf("x:");
		for(i = 0; i < 5; i++){
			printf("%d ", x[i]);
		}
		printf("\n");
		printf("y:");
		for(i = 0; i < 5; i++){
			printf("%d ", y[i]);
		}
		printf("\n");
*/
		vector<vector<edge> > g(25, vector<edge>());
		for(i = 0; i < 5; i++){
			if(S[x[i]] == 'W'){
				for(j = 1; j < 5; j++){
					g[align(i, j)].push_back(edge(align(i, j - 1), y[j] - y[j - 1]));
				}
			}
			else{
				for(j = 0; j < 4; j++){
					g[align(i, j)].push_back(edge(align(i, j + 1), y[j + 1] - y[j]));
				}
			}
		}
		for(j = 0; j < 5; j++){
			if(T[y[j]] == 'N'){
				for(i = 1; i < 5; i++){
					g[align(i, j)].push_back(edge(align(i - 1, j), x[i] - x[i - 1]));
				}
			}
			else{
				for(i = 0; i < 4; i++){
					g[align(i, j)].push_back(edge(align(i + 1, j), x[i + 1] - x[i]));
				}
			}
		}
		int s, t;
		for(i = 0; i < 25; i++){
			if(x[i / 5] == a && y[i % 5] == b){
				s = i;
				break;
			}
		}
		for(i = 0; i < 25; i++){
			if(x[i / 5] == c && y[i % 5] == d){
				t = i;
				break;
			}
		}
/*		for(i = 0; i < 25; i++){
			printf("edge[%d]:", i);
			for(j = 0; j < g[i].size(); j++){
				printf("(%d, %d) ", g[i][j].to, g[i][j].cost);
			}
			printf("\n");
		}
		printf("(s, t) = (%d, %d)\n", s, t);
*/		vector<int> res = dijkstra(g, s);
		if(res[t] == inf){
			printf("-1\n");
		}
		else{
			printf("%d\n", res[t]);
		}
	}
	return 0;
}