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>

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}

std::vector<bool> data[2];
std::vector<int> next[2][2], prev[2][2];

struct Info {
	int lower;
	int upper;
	int con;
};

#define INF 1000000000

int res;
int n[2];
int goal[2];
int goal_adj[2][2][2]; // axis, dir, what
std::vector<Info> used[2];
int depth;
void dfs(int x, int y, bool next_axis, int cost) {
	if (depth >= 6) return;
	// fprintf(stderr, "(%d, %d) dir:%d cost:%d\n", x, y, next_axis, cost);
	int axis_pos = next_axis ? y : x;
	int axis_start = next_axis ? x : y;
	if (x == goal[0] && y == goal[1]) {
		res = std::min(res, cost);
		return;
	} else if (!next_axis && x == goal[0] && (y < goal[1]) == data[next_axis][axis_pos]) {
		res = std::min(res, cost + std::abs(y - goal[1]));
		return;
	} else if (next_axis && y == goal[1] && (x < goal[0]) == data[next_axis][axis_pos]) {
		res = std::min(res, cost + std::abs(x - goal[0]));
		return;
	}
	auto trial = [&] (int next_pos) {
		for (auto i : used[!next_axis]) {
			if ((i.con < axis_start) == (axis_start < next_pos) && axis_pos >= i.lower && axis_pos <= i.upper) return;
			if (i.con == next_pos && axis_pos >= i.lower && axis_pos <= i.upper) return;
		}
		depth++;
		used[next_axis].push_back({axis_start, next_pos > axis_pos ? axis_pos : -INF, next_pos > axis_pos ? INF : next_pos});
		dfs(next_axis ? next_pos : x, next_axis ? y : next_pos, !next_axis, cost + std::abs(axis_start - next_pos));
		used[next_axis].pop_back();
		depth--;
	};
	if (data[next_axis][axis_pos]) { // positive
		if (goal[!next_axis] > axis_start) {
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					int r0 = goal_adj[!next_axis][j][i];
					if (r0 != -1 && r0 > axis_start) trial(r0);
				}
			}
		} else for (int i = 0; i < 2; i++)
			if (next[!next_axis][i][axis_start] != -1) trial(next[!next_axis][i][axis_start]);
	} else {
		if (goal[!next_axis] < axis_start) {
			for (int i = 0; i < 2; i++) {
				for (int j = 0; j < 2; j++) {
					int r0 = goal_adj[!next_axis][j][i];
					if (r0 != -1 && r0 < axis_start) trial(r0);
				}
			}
		} else for (int i = 0; i < 2; i++) if (prev[!next_axis][i][axis_start] != -1) trial(prev[!next_axis][i][axis_start]);
	}
}

int main() {
	n[0] = ri();
	n[1] = ri();
	int q = ri();
	{
		std::string s, t;
		std::cin >> s >> t;
		data[0].resize(n[0]);
		data[1].resize(n[1]);
		for (int i = 0; i < n[0]; i++) data[0][i] = s[i] == 'E';
		for (int i = 0; i < n[1]; i++) data[1][i] = t[i] == 'S';
	}
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
		int n = data[i].size();
		next[i][j].resize(n);
		prev[i][j].resize(n);
		next[i][j][n - 1] = -1;
		for (int k = n; --k; ) {
			if (data[i][k] == j) next[i][j][k - 1] = k;
			else next[i][j][k - 1] = next[i][j][k];
		}
		prev[i][j][0] = -1;
		for (int k = 0; k + 1 < n; k++) {
			if (data[i][k] == j) prev[i][j][k + 1] = k;
			else prev[i][j][k + 1] = prev[i][j][k];
		}
	}
	/*
	for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) {
		std::cerr << "axis:" << i << " what:" << j << "  : ";
		for (auto k : next[i][j]) std::cerr << k << " ";
		std::cerr << std::endl;
	}*/
	
	for (int i = 0; i < q; i++) {
		int sx = ri() - 1;
		int sy = ri() - 1;
		goal[0]	= ri() - 1;
		goal[1] = ri() - 1;
		for (int j = 0; j < 2; j++) for (int k = 0; k < 2; k++) {
			goal_adj[j][0][k] = data[j][goal[j]] == k ? goal[j] : prev[j][k][goal[j]];
			goal_adj[j][1][k] = data[j][goal[j]] == k ? goal[j] : next[j][k][goal[j]];
		}
		// std::cerr << "!" << goal_adj[1][0][0] << " " << goal_adj[1][0][1] << std::endl;
		res = INF;
		dfs(sx, sy, false, 0);
		dfs(sx, sy, true, 0);
		printf("%d\n", res == INF ? -1 : res);
	}
	
	return 0;
}