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 "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
const long long int exa = 1000000000000000000;
//const int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

struct Node {
	int x, y, turn, dis;
	Node(int a, int b, int c = 0, int d = 0) {
		y = a, x = b;
		turn = c;
		dis = d;
	}
};

int border = 4;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> H >> W >> K;
	string s, t;
	cin >> s >> t;
	vector<int>ldif(W, -1);
	vector<int>rdif(W, -1);
	for (int i = 1; i < W; i++) {
		if (t[i] == t[i - 1])ldif[i] = ldif[i - 1];
		else ldif[i] = i - 1;
	}
	for (int i = W - 2; i >= 0; i--) {
		if (t[i] == t[i + 1])rdif[i] = rdif[i + 1];
		else rdif[i] = i + 1;
	}
	vector<int>udif(H, -1);
	vector<int>ddif(H, -1);
	for (int i = 1; i < H; i++) {
		if (s[i] == s[i - 1])udif[i] = udif[i - 1];
		else udif[i] = i - 1;
	}
	for (int i = H - 2; i >= 0; i--) {
		if (s[i] == s[i + 1])ddif[i] = ddif[i + 1];
		else ddif[i] = i + 1;
	}
	vector<int>ret;
	for (int i = 0; i < K; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		a--, b--, c--, d--;
		queue<Node>Q;
		Q.push(Node(a, b));
		int ans = MOD;
		while (!Q.empty()) {
			auto cn = Q.front();
			Q.pop();
			//cerr << cn.y << " " << cn.x << " " << cn.turn << " " << cn.dis << endl;
			if (cn.y == c && cn.x == d) {
				ans = min(ans, cn.dis);
				continue;
			}
			if (cn.turn == border)break;
			if (t[cn.x] == 'N') {//(-,0)
				if (c <= cn.y && ((s[c] == 'W'&&cn.x >= d) || (s[c] == 'E'&&cn.x <= d))) {
					ans = min(ans, cn.dis + abs(c - cn.y) + abs(cn.x - d));
					continue;
				}
				else if (c <= cn.y) {
					if (udif[cn.y] != -1) {
						Q.push({ Node(udif[cn.y],cn.x,cn.turn + 1,cn.dis + abs(cn.y - udif[cn.y])) });
					}
					if (udif[c] != -1 && udif[c] != udif[cn.y]) {
						Q.push(Node(udif[c], cn.x, cn.turn + 1, cn.dis + abs(cn.y - udif[c])));
					}
				}
				else {
					if (udif[cn.y] != -1) {
						Q.push({ Node(udif[cn.y],cn.x,cn.turn + 1,cn.dis + abs(cn.y - udif[cn.y])) });
					}
				}
			}
			else {
				if (c >= cn.y && ((s[c] == 'W'&&cn.x >= d) || (s[c] == 'E'&&cn.x <= d))) {
					ans = min(ans, cn.dis + abs(c - cn.y) + abs(cn.x - d));
					continue;
				}
				else if (c >= cn.y) {
					if (ddif[cn.y] != -1) {
						Q.push(Node(ddif[cn.y], cn.x, cn.turn + 1, cn.dis + abs(cn.y - ddif[cn.y])));
					}
					if (ddif[c] != -1 && ddif[c] != ddif[cn.y]) {
						Q.push(Node(ddif[c], cn.x, cn.turn + 1, cn.dis + abs(cn.y - ddif[c])));
					}
				}
				else {
					if (ddif[cn.y] != -1) {
						Q.push(Node(ddif[cn.y], cn.x, cn.turn + 1, cn.dis + abs(cn.y - ddif[cn.y])));
					}
				}
			}
			if (s[cn.y] == 'W') {
				if (d <= cn.x && ((t[d] == 'N'&&cn.y >= c) || (t[d] == 'S'&&cn.y <= c))) {
					ans = min(ans, cn.dis + abs(d - cn.x) + abs(cn.y - c));
					continue;
				}
				else if(d<=cn.x){
					if (ldif[cn.x] != -1) {
						Q.push(Node(cn.y, ldif[cn.x], cn.turn + 1, cn.dis + abs(cn.x - ldif[cn.x])));
					}
					if (ldif[d] != -1 && ldif[d] != ldif[cn.x]) {
						Q.push(Node(cn.y, ldif[d], cn.turn + 1, cn.dis + abs(cn.x - ldif[d])));
					}
				}
				else {
					if (ldif[cn.x] != -1) {
						Q.push(Node(cn.y, ldif[cn.x], cn.turn + 1, cn.dis + abs(cn.x - ldif[cn.x])));
					}
				}
			}
			else {
				if (d >= cn.x && ((t[d] == 'N'&&cn.y >= c) || (t[d] == 'S'&&cn.y <= c))) {
					ans = min(ans, cn.dis + abs(d - cn.x) + abs(cn.y - c));
					continue;
				}
				else if(d>=cn.x){
					if (rdif[cn.x] != -1) {
						Q.push(Node(cn.y, rdif[cn.x], cn.turn + 1, cn.dis + abs(cn.x - rdif[cn.x])));
					}
					if (rdif[d] != -1 && rdif[d] != rdif[cn.x]) {
						Q.push(Node(cn.y, rdif[d], cn.turn + 1, cn.dis + abs(cn.x - rdif[d])));
					}
				}
				else {
					if (rdif[cn.x] != -1) {
						Q.push(Node(cn.y, rdif[cn.x], cn.turn + 1, cn.dis + abs(cn.x - rdif[cn.x])));
					}
				}
			}
		}
		if (ans == MOD)ans = -1;
		ret.push_back(ans);
	}
	for (auto i : ret)cout << i << endl;
	return 0;
}