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 <cstdint>
#include <type_traits>
#include <algorithm>
#include <iterator>
#include <iostream>
#include <vector>
#include <string>
#include <initializer_list>
namespace loquat {
namespace bitmanip {
template <typename T>
inline auto ctz(T x) noexcept ->
	typename std::enable_if<sizeof(T) <= sizeof(int), unsigned int>::type
{
	return __builtin_ctz(x);
}
template <typename T>
inline auto ctz(T x) noexcept ->
	typename std::enable_if<sizeof(int) < sizeof(T), unsigned int>::type
{
	return __builtin_ctzll(x);
}
template <typename T>
inline auto clz(T x) noexcept ->
	typename std::enable_if<sizeof(int) < sizeof(T), unsigned int>::type
{
	return __builtin_clzll(x);
}
template <typename T>
inline T flp2(T x) noexcept {
	if(x == 0u){ return 0u; }
	return T(1u) << (sizeof(T) * 8u - 1u - clz(x));
}
}
}
namespace loquat {
template <typename Impl>
class range_query_behavior_wrapper {
public:
	using value_type = typename Impl::value_type;
private:
	Impl m_impl;
public:
	range_query_behavior_wrapper(Impl impl) : m_impl(std::move(impl)) { }
	value_type identity() const {
		return m_impl.identity();
	}
	value_type merge(const value_type& a, const value_type& b) const {
		return m_impl.merge(a, b);
	}
};
}
namespace loquat {
template <typename Behavior>
class nazo_table {
public:
	using behavior_type = Behavior;
	using value_type = typename behavior_type::value_type;
private:
	std::vector<std::vector<value_type>> m_table;
	range_query_behavior_wrapper<behavior_type> m_behavior;
	template <typename Iterator>
	void forward_fill(Iterator it, int row, int first, int last){
		value_type acc = m_behavior.identity();
		m_table[row][first] = acc;
		for(int i = first + 1; i < last; ++i, ++it){
			acc = m_behavior.merge(acc, *it);
			m_table[row][i] = acc;
		}
	}
	template <typename Iterator>
	void backward_fill(Iterator it, int row, int first, int last){
		value_type acc = m_behavior.identity();
		--it;
		for(int i = first - 1; i >= last; --i, --it){
			acc = m_behavior.merge(*it, acc);
			m_table[row][i] = acc;
		}
	}
	template <typename Iterator>
	void fill_table(Iterator first, Iterator last){
		const int n = std::distance(first, last);
		Iterator it = std::next(first);
		for(int i = 1; i <= n; ++i, ++it){
			const int s = bitmanip::ctz(i);
			while(m_table.size() <= static_cast<size_t>(s)){
				m_table.emplace_back(n + 1);
			}
			backward_fill(it, s, i, i - (1 << s));
			forward_fill(it, s, i, std::min(n + 1, i + (1 << s)));
		}
	}
public:
	template <typename Iterator>
	nazo_table(
		Iterator first,
		Iterator last,
		const behavior_type& behavior = behavior_type())
		: m_table()
		, m_behavior(behavior)
	{
		fill_table(first, last);
	}
	value_type query(size_t l, size_t r) const {
		if(l == r){ return m_behavior.identity(); }
		const int s = bitmanip::ctz(bitmanip::flp2(l ^ r));
		return m_behavior.merge(m_table[s][l], m_table[s][r]);
	}
};
}
using namespace std;
static const int INF = 1000000000;
struct min_behavior {
	using value_type = int;
	value_type identity() const { return numeric_limits<int>::max(); }
	value_type merge(const value_type& a, const value_type& b) const { return min(a, b); }
};
struct max_behavior {
	using value_type = int;
	value_type identity() const { return numeric_limits<int>::min(); }
	value_type merge(const value_type& a, const value_type& b) const { return max(a, b); }
};
int solve(
	int depth, int a, int b, int c, int d,
	const string& hor, const string& ver,
	const loquat::nazo_table<min_behavior>& min_w,
	const loquat::nazo_table<max_behavior>& max_w,
	const loquat::nazo_table<min_behavior>& min_e,
	const loquat::nazo_table<max_behavior>& max_e,
	const loquat::nazo_table<min_behavior>& min_n,
	const loquat::nazo_table<max_behavior>& max_n,
	const loquat::nazo_table<min_behavior>& min_s,
	const loquat::nazo_table<max_behavior>& max_s)
{
	if(depth >= 5){ return INF; }
	const int n = hor.size(), m = ver.size();
	int answer = INF;
	if(hor[a] == 'W' || hor[a] == 'N'){
		if(d < b){
			if(a == c){ answer = min(answer, b - d); }
			const int x1 = max_n.query(0, b + 1);
			if(x1 >= 0){ answer = min(answer, solve(depth + 1, x1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - x1)); }
			const int y1 = max_s.query(0, b + 1);
			if(y1 >= 0){ answer = min(answer, solve(depth + 1, y1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - y1)); }
			const int x2 = max_n.query(0, d + 1);
			if(x2 >= 0 && x1 != x2){ answer = min(answer, solve(depth + 1, x2, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - x2)); }
			const int y2 = max_s.query(0, d + 1);
			if(y2 >= 0 && y1 != y2){ answer = min(answer, solve(depth + 1, y2, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - y2)); }
		}else{
			const int x1 = max_n.query(0, b + 1);
			if(x1 >= 0){ answer = min(answer, solve(depth + 1, x1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - x1)); }
			const int y1 = max_s.query(0, b + 1);
			if(y1 >= 0){ answer = min(answer, solve(depth + 1, y1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (b - y1)); }
		}
	}else{
		if(d > b){
			if(a == c){ answer = min(answer, d - b); }
			const int x1 = min_n.query(b, m);
			if(x1 < m){ answer = min(answer, solve(depth + 1, x1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (x1 - b)); }
			const int y1 = min_s.query(b, m);
			if(y1 < m){ answer = min(answer, solve(depth + 1, y1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (y1 - b)); }
			const int x2 = min_n.query(d, m);
			if(x2 < m && x1 != x2){ answer = min(answer, solve(depth + 1, x2, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (x2 - b)); }
			const int y2 = min_s.query(d, m);
			if(y2 < m && y1 != y2){ answer = min(answer, solve(depth + 1, y2, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (y2 - b)); }
		}else{
			const int x1 = min_n.query(b, m);
			if(x1 < m){ answer = min(answer, solve(depth + 1, x1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (x1 - b)); }
			const int y1 = min_s.query(b, m);
			if(y1 < m){ answer = min(answer, solve(depth + 1, y1, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e) + (y1 - b)); }
		}
	}
	return answer;
}
int main(){
	ios_base::sync_with_stdio(false);
	int n, m, q;
	string hor, ver;
	cin >> n >> m >> q >> hor >> ver;
	vector<int> min_w_init(n, numeric_limits<int>::max());
	vector<int> max_w_init(n, numeric_limits<int>::min());
	vector<int> min_e_init(n, numeric_limits<int>::max());
	vector<int> max_e_init(n, numeric_limits<int>::min());
	vector<int> min_n_init(m, numeric_limits<int>::max());
	vector<int> max_n_init(m, numeric_limits<int>::min());
	vector<int> min_s_init(m, numeric_limits<int>::max());
	vector<int> max_s_init(m, numeric_limits<int>::min());
	for(int i = 0; i < n; ++i){
		if(hor[i] == 'W'){
			min_w_init[i] = i;
			max_w_init[i] = i;
		}else{
			min_e_init[i] = i;
			max_e_init[i] = i;
		}
	}
	for(int i = 0; i < m; ++i){
		if(ver[i] == 'N'){
			min_n_init[i] = i;
			max_n_init[i] = i;
		}else{
			min_s_init[i] = i;
			max_s_init[i] = i;
		}
	}
	const loquat::nazo_table<min_behavior> min_w(min_w_init.begin(), min_w_init.end());
	const loquat::nazo_table<max_behavior> max_w(max_w_init.begin(), max_w_init.end());
	const loquat::nazo_table<min_behavior> min_e(min_e_init.begin(), min_e_init.end());
	const loquat::nazo_table<max_behavior> max_e(max_e_init.begin(), max_e_init.end());
	const loquat::nazo_table<min_behavior> min_n(min_n_init.begin(), min_n_init.end());
	const loquat::nazo_table<max_behavior> max_n(max_n_init.begin(), max_n_init.end());
	const loquat::nazo_table<min_behavior> min_s(min_s_init.begin(), min_s_init.end());
	const loquat::nazo_table<max_behavior> max_s(max_s_init.begin(), max_s_init.end());
	while(q--){
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		--a; --b; --c; --d;
		const int answer = min(
		 	solve(0, a, b, c, d, hor, ver, min_w, max_w, min_e, max_e, min_n, max_n, min_s, max_s),
		 	solve(0, b, a, d, c, ver, hor, min_n, max_n, min_s, max_s, min_w, max_w, min_e, max_e));
		if(answer >= INF){
			cout << -1 << "\n";
		}else{
			cout << answer << "\n";
		}
	}
	return 0;
}