问题陈述

在AtCoder共和国的高波市，有 $N$ 条东西向的道路和 $M$ 条南北向的道路。其他地方没有道路。从北向南的第 $i$ 条东西向道路和从西向东的第 $j$ 条南北向道路在交叉口 $(i, j)$ 相交。两条东西向道路不相交，两条南北向道路也不相交。同一方向上相邻道路之间的距离为 $1$。

每条道路都是单行道，只能朝一个方向行走。每条道路允许的方向由长度为 $N$ 的字符串 $S$ 和长度为 $M$ 的字符串 $T$ 描述，规则如下：

• 如果 $S$ 的第 $i$ 个字符是 W，则只能沿着从北向南的第 $i$ 条东西向道路向西走；
• 如果 $S$ 的第 $i$ 个字符是 E，则只能沿着从北向南的第 $i$ 条东西向道路向东走；
• 如果 $T$ 的第 $i$ 个字符是 N，则只能沿着从西向东的第 $i$ 条南北向道路向北走；
• 如果 $T$ 的第 $i$ 个字符是 S，则只能沿着从西向东的第 $i$ 条南北向道路向南走。

处理以下 $Q$ 个查询：

• 第 $i$ 个查询中给出了 $a_i, b_i, c_i$ 和 $d_i$。沿着道路行走，从交叉口 $(a_i, b_i)$ 到达交叉口 $(c_i, d_i)$ 的最小距离是多少？

约束条件

• $2 \leq N \leq 100000$
• $2 \leq M \leq 100000$
• $2 \leq Q \leq 200000$
• $|S| = N$
• $S$ 由 W 和 E 组成。
• $|T| = M$
• $T$ 由 N 和 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)$

输入

输入格式如下，从标准输入读入：

$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$

输出

第 $i$ 行输出第 $i$ 个查询的响应。如果无法沿道路到达交叉口 $(c_i, d_i)$，则输出 -1。

样例输入 1

4 5 4
EEWW
NSNNS
4 1 1 4
1 3 1 2
4 2 3 2
3 3 3 5

样例输出 1

6
11
5
4

每条道路允许的方向如下图所示（北向上）：

对于这四个查询中的每一个，实现最小行程距离的路径如下所示：

样例输入 2

3 3 2
EEE
SSS
1 1 3 3
3 3 1 1

样例输出 2

4
-1

可能无法到达目的地。

样例输入 3

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

样例输出 3

9
-1
4
9
2
3
7
7
6
-1