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 <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <cstdlib>
#define llint long long
#define inf 100000000000000000


using namespace std;
typedef pair<llint, llint> P;

struct edge{
	llint to, cost;
	edge(){}
	edge(llint a, llint b){
		to = a, cost = b;
	}
};

llint H, W, Q;
string s, t;
llint prel[200005], prer[200005], nextl[200005], nextr[200005];
llint preu[200005], pred[200005], nextu[200005], nextd[200005];
vector<llint> vecx, vecy;
vector<edge> G[205];
llint dist[205];
llint S, T, V;

void dijkstra()
{
	for(llint i = 0; i < V; i++) dist[i] = inf;
	dist[S] = 0;
	
	priority_queue< P, vector<P>, greater<P> > PQ;
	PQ.push( make_pair(0, S) );
	
	llint v, d;
	while(PQ.size()){
		d = PQ.top().first;
		v = PQ.top().second;
		PQ.pop();
		if(dist[v] < d) continue;
		for(llint i = 0; i < G[v].size(); i++){
			if(dist[G[v][i].to] > d + G[v][i].cost){
				dist[G[v][i].to] = d + G[v][i].cost;
				PQ.push( make_pair(dist[G[v][i].to], G[v][i].to) );
			}
		}
	}
}

void make(llint s, llint g, vector<llint> &vec, llint N, llint preu[], llint pred[], llint nextu[], llint nextd[])
{
	vec.clear();
	vec.push_back(s);
	vec.push_back(preu[s]);
	vec.push_back(pred[s]);
	vec.push_back(nextu[s]);
	vec.push_back(nextd[s]);
	vec.push_back(g);
	vec.push_back(preu[g]);
	vec.push_back(pred[g]);
	vec.push_back(nextu[g]);
	vec.push_back(nextd[g]);
	
	sort(vec.begin(), vec.end());
	vec.erase(unique(vec.begin(), vec.end()), vec.end());
	if(vec.front() == 0) vec.erase(vec.begin());
	if(vec.back() == N+1) vec.erase(vec.end()-1);
}

int main(void)
{
	cin >> H >> W >> Q;
	cin >> s >> t;
	s = "#" + s + "#"; t = "#" + t + "#";
	
	prel[0] = 0, prer[0] = 0;
	for(llint i = 1; i <= H; i++){
		prel[i] = prel[i-1];
		prer[i] = prer[i-1];
		if(s[i-1] == 'W') prel[i] = i-1;
		if(s[i-1] == 'E') prer[i] = i-1;
	}
	nextl[H+1] = H+1, nextr[H+1] = H+1;
	for(llint i = H; i >= 1; i--){
		nextl[i] = nextl[i+1];
		nextr[i] = nextr[i+1];
		if(s[i+1] == 'W') nextl[i] = i+1;
		if(s[i+1] == 'E') nextr[i] = i+1;
	}
	
	preu[0] = 0, pred[0] = 0;
	for(llint i = 1; i <= W; i++){
		preu[i] = preu[i-1];
		pred[i] = pred[i-1];
		if(t[i-1] == 'N') preu[i] = i-1;
		if(t[i-1] == 'S') pred[i] = i-1;
	}
	nextu[W+1] = W+1, nextd[W+1] = W+1;
	for(llint i = W; i >= 1; i--){
		nextu[i] = nextu[i+1];
		nextd[i] = nextd[i+1];
		if(t[i+1] == 'N') nextu[i] = i+1;
		if(t[i+1] == 'S') nextd[i] = i+1;
	}
	
	llint sx, sy, gx, gy;
	for(llint q = 0; q < Q; q++){
		cin >> sy >> sx >> gy >> gx;
		make(sx, gx, vecx, W, preu, pred, nextu, nextd);
		make(sy, gy, vecy, H, prel, prer, nextl, nextr);
		
		llint w = vecx.size(), h = vecy.size();
		for(llint i = 0; i < w*h; i++) G[i].clear();
		for(llint x = 0; x < w; x++){
			for(llint y = 0; y < h; y++){
				llint nx = x, ny = y;
				if(t[vecx[x]] == 'N') ny--;
				else ny++;
				if(ny >= 0 && ny < h){
					G[x+y*w].push_back(edge(nx+ny*w, abs(vecy[y]-vecy[ny])));
				}
				nx = x, ny = y;
				if(s[vecy[y]] == 'W') nx--;
				else nx++;
				if(nx >= 0 && nx < w){
					G[x+y*w].push_back(edge(nx+ny*w, abs(vecx[x]-vecx[nx])));
				}
			}
		}
		llint SX, GX, SY, GY;
		for(llint i = 0; i < w; i++){
			if(vecx[i] == sx) SX = i;
			if(vecx[i] == gx) GX = i;
		}
		for(llint i = 0; i < h; i++){
			if(vecy[i] == sy) SY = i;
			if(vecy[i] == gy) GY = i;
		}
		S = SX + SY*w, T = GX + GY*w, V = w*h;
		
		dijkstra();
		if(dist[T] >= inf) cout << -1 << "\n";
		else cout << dist[T] << "\n";
	}
	flush(cout);
	
	return 0;
}