对于你来说，EJOI 是什么？ 游戏室！

Teo 正在寻找克罗地亚 EJOI 队！她已经找到了 Gabriel，但仍在寻找 Vito、Dino 和 Ivo。

Teo 和 EJOI 队身处一个由 $n \times m$ 个大小相同的房间组成的迷宫中。这些房间构成了一个网格。左上角的房间标记为 $(1, 1)$，右下角的房间标记为 $(n, m)$。在每两个相邻的房间之间，都有一扇门，门有四种颜色：蓝色（标记为 'P'）、红色（标记为 'C'）、绿色（标记为 'Z'）和橙色（标记为 'N'）。

第三个样例的示意图。黑圈标记了第四个询问中 Teo 和 Gabriel 所在的房间，白圈标记了 Vito、Ivo 和 Dino 所在的房间。灰色路径是穿过三种不同颜色门的一条可能路径。

在某个时刻，Gabriel 说：我知道其他人都在哪里，但只有你能回答我所有的问题，我才会告诉你。

Gabriel 的问题是：如果我们当前在房间 $(a_i, b_i)$，而其他人都在房间 $(c_i, d_i)$，那么我们到达他们那里所经过的门的最少颜色数量是多少？

Teo 非常擅长回答 Gabriel 的问题，但问题实在太多了。她没有太多时间（巴士很快就要开了），所以她请求你帮她回答 Gabriel 的 $q$ 个问题！

输入格式

第一行包含整数 $n$ 和 $m$ ($1 \le n, m \le 100, 1 < n \times m$)，表示房间的数量。

接下来的 $n$ 行，第 $i$ 行包含 $m - 1$ 个字符（'P'、'C'、'Z' 或 'N'），其中第 $j$ 个字符表示连接房间 $(i, j)$ 和 $(i, j + 1)$ 的门的颜色。

接下来的 $n - 1$ 行，第 $i$ 行包含 $m$ 个字符（'P'、'C'、'Z' 或 'N'），其中第 $j$ 个字符表示连接房间 $(i, j)$ 和 $(i + 1, j)$ 的门的颜色。

下一行包含整数 $q$ ($1 \le q \le 100$)，表示 Gabriel 问题的数量。

接下来的 $q$ 行中，第 $i$ 行包含四个整数 $a_i, b_i, c_i, d_i$ ($1 \le a_i, c_i \le n, 1 \le b_i, d_i \le m, (a_i, b_i) \neq (c_i, d_i)$)，描述 Gabriel 的第 $i$ 个问题。

输出格式

在 $q$ 行中，第 $i$ 行输出 Gabriel 第 $i$ 个问题的答案。

子任务

样例

输入 1

1 8
CPZNCCP
4
1 1 1 8
1 3 1 5
1 8 1 4
1 2 1 3

输出 1

4
2
3
1

输入 2

3 3
PP
PP
PP
CCC
CCC
3
1 1 3 3
3 3 2 2
1 1 1 3

输出 2

2
2
1

输入 3

4 4
CCC
CPC
PPP
CNP
ZZZZ
PPPP
CPZC
4
3 1 2 3
1 1 4 4
2 2 3 3
1 4 4 1

输出 3

1
2
1
3

说明

第三个样例已在文中说明。

对于第一个问题，Teo 和 Gabriel 可以仅使用蓝色门到达其他人所在处；对于第二个问题，他们可以使用蓝色和绿色门；对于第三个问题，仅使用蓝色门就足够了；对于第四个问题，他们可以使用蓝色、绿色和红色门。