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 <queue>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

int N, M, Q; string S, T;
vector<int>X1, X2, Y1, Y2;
vector<int>needX[100009], needY[100009];

void get_x() {
	for (int i = 0; i < N; i++) {
		if (S[i] == 'E') {
			needX[i].push_back(i);
			int pos1 = lower_bound(X2.begin(), X2.end(), i) - X2.begin(); pos1--;
			int pos2 = pos1 + 1;

			if (pos1 >= 0 && pos1 < X2.size()) {
				needX[i].push_back(X2[pos1]);
				int pos3 = lower_bound(X1.begin(), X1.end(), X2[pos1]) - X1.begin(); pos3--;
				if (pos3 >= 0) needX[i].push_back(X1[pos3]);
			}
			if (pos2 >= 0 && pos2 < X2.size()) {
				needX[i].push_back(X2[pos2]);
				int pos3 = lower_bound(X1.begin(), X1.end(), X2[pos2]) - X1.begin();
				if (pos3 < X1.size()) needX[i].push_back(X1[pos3]);
			}
		}
		if (S[i] == 'W') {
			needX[i].push_back(i);
			int pos1 = lower_bound(X1.begin(), X1.end(), i) - X1.begin(); pos1--;
			int pos2 = pos1 + 1;

			if (pos1 >= 0 && pos1 < X1.size()) {
				needX[i].push_back(X1[pos1]);
				int pos3 = lower_bound(X2.begin(), X2.end(), X1[pos1]) - X2.begin(); pos3--;
				if (pos3 >= 0) needX[i].push_back(X2[pos3]);
			}
			if (pos2 >= 0 && pos2 < X1.size()) {
				needX[i].push_back(X1[pos2]);
				int pos3 = lower_bound(X2.begin(), X2.end(), X1[pos2]) - X2.begin();
				if (pos3 < X2.size()) needX[i].push_back(X2[pos3]);
			}
		}
	}
}

void get_y() {
	for (int i = 0; i < M; i++) {
		if (T[i] == 'N') {
			needY[i].push_back(i);
			int pos1 = lower_bound(Y2.begin(), Y2.end(), i) - Y2.begin(); pos1--;
			int pos2 = pos1 + 1;

			if (pos1 >= 0 && pos1 < Y2.size()) {
				needY[i].push_back(Y2[pos1]);
				int pos3 = lower_bound(Y1.begin(), Y1.end(), Y2[pos1]) - Y1.begin(); pos3--;
				if (pos3 >= 0) needY[i].push_back(Y1[pos3]);
			}
			if (pos2 >= 0 && pos2 < Y2.size()) {
				needY[i].push_back(Y2[pos2]);
				int pos3 = lower_bound(Y1.begin(), Y1.end(), Y2[pos2]) - Y1.begin();
				if (pos3 < Y1.size()) needY[i].push_back(Y1[pos3]);
			}
		}
		if (T[i] == 'S') {
			needY[i].push_back(i);
			int pos1 = lower_bound(Y1.begin(), Y1.end(), i) - Y1.begin(); pos1--;
			int pos2 = pos1 + 1;

			if (pos1 >= 0 && pos1 < Y1.size()) {
				needY[i].push_back(Y1[pos1]);
				int pos3 = lower_bound(Y2.begin(), Y2.end(), Y1[pos1]) - Y2.begin(); pos3--;
				if (pos3 >= 0) needY[i].push_back(Y2[pos3]);
			}
			if (pos2 >= 0 && pos2 < Y1.size()) {
				needY[i].push_back(Y1[pos2]);
				int pos3 = lower_bound(Y2.begin(), Y2.end(), Y1[pos2]) - Y2.begin();
				if (pos3 < Y2.size()) needY[i].push_back(Y2[pos3]);
			}
		}
	}
}

char u[10], v[10]; int dist[10][10];

int solve(int ax, int ay, int bx, int by) {
	vector<int>X, Y;
	for (int i : needX[ax]) X.push_back(i);
	for (int i : needX[bx]) X.push_back(i);
	for (int i : needY[ay]) Y.push_back(i);
	for (int i : needY[by]) Y.push_back(i);
	sort(X.begin(), X.end()); X.erase(unique(X.begin(), X.end()), X.end());
	sort(Y.begin(), Y.end()); Y.erase(unique(Y.begin(), Y.end()), Y.end());

	for (int i = 0; i < X.size(); i++) u[i] = S[X[i]];
	for (int i = 0; i < Y.size(); i++) v[i] = T[Y[i]];

	for (int i = 0; i < 10; i++) { for (int j = 0; j < 10; j++) dist[i][j] = (1 << 30); }

	int sx = lower_bound(X.begin(), X.end(), ax) - X.begin();
	int sy = lower_bound(Y.begin(), Y.end(), ay) - Y.begin();
	int gx = lower_bound(X.begin(), X.end(), bx) - X.begin();
	int gy = lower_bound(Y.begin(), Y.end(), by) - Y.begin();

	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>que;
	dist[sx][sy] = 0; que.push(make_pair(0, sx * 16 + sy));

	while (!que.empty()) {
		int G = que.top().second; que.pop();
		int lx = (G >> 4), ly = (G & 15);

		// EW 方面
		if (u[lx] == 'E') {
			if (ly + 1 < Y.size() && dist[lx][ly + 1] > dist[lx][ly] + (Y[ly + 1] - Y[ly])) {
				dist[lx][ly + 1] = dist[lx][ly] + (Y[ly + 1] - Y[ly]);
				que.push(make_pair(dist[lx][ly + 1], G + 1));
			}
		}
		if (u[lx] == 'W') {
			if (ly > 0 && dist[lx][ly - 1] > dist[lx][ly] + (Y[ly] - Y[ly - 1])) {
				dist[lx][ly - 1] = dist[lx][ly] + (Y[ly] - Y[ly - 1]);
				que.push(make_pair(dist[lx][ly - 1], G - 1));
			}
		}

		// NS 方面
		if (v[ly] == 'N') {
			if (lx > 0 && dist[lx - 1][ly] > dist[lx][ly] + (X[lx] - X[lx - 1])) {
				dist[lx - 1][ly] = dist[lx][ly] + (X[lx] - X[lx - 1]);
				que.push(make_pair(dist[lx - 1][ly], G - 16));
			}
		}
		if (v[ly] == 'S') {
			if (lx + 1 < X.size() && dist[lx + 1][ly] > dist[lx][ly] + (X[lx + 1] - X[lx])) {
				dist[lx + 1][ly] = dist[lx][ly] + (X[lx + 1] - X[lx]);
				que.push(make_pair(dist[lx + 1][ly], G + 16));
			}
		}
	}
	if (dist[gx][gy] == (1 << 30)) return -1;
	return dist[gx][gy];
}

int main() {
	cin >> N >> M >> Q;
	cin >> S >> T;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == 'E') X1.push_back(i);
		if (S[i] == 'W') X2.push_back(i);
	}
	for (int i = 0; i < T.size(); i++) {
		if (T[i] == 'N') Y1.push_back(i);
		if (T[i] == 'S') Y2.push_back(i);
	}
	
	get_x();
	get_y();

	for (int i = 1; i <= Q; i++) {
		int ax, ay, bx, by;
		scanf("%d%d%d%d", &ax, &ay, &bx, &by);
		ax--; ay--; bx--; by--;
		printf("%d\n", solve(ax, ay, bx, by));
	}
	return 0;
}