该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Labirint

迷宫路径颜色数

题目描述

$Teo$和克罗地亚$EJOI$队伍在一个迷宫里面。

这个迷宫是一个$n \times m$的网格，用坐标$(1,1)$表示左上角的单元格，用坐标$(n,m)$表示右下角的单元格。每一对相邻（四连通，即与上、下、左、右相邻）的单元格之间都有一道门，门有四种颜色：蓝、红、绿、橙，分别用字符$P$、$C$、$Z$、$N$表示。只能通过门移动到其它单元格。

现在$Teo$给你$q$组询问，每次询问给定$a$，$b$，$c$，$d$，表示找到一条从$(a,b)$到$(c,d)$的路径，最小化经过的门的颜色数，请你回答最少的颜色数量。

输入格式

第一行两个整数$n$，$m$表示网格的行数和列数。

接下来一个$n$行$m-1$列的字符矩阵，其中第$i$行第$j$列的字符表示$(i,j)$和$(i,j+1)$之间的门的颜色。

接下来一个$n-1$行$m$列的字符矩阵，其中第$i$行第$j$列的字符表示$(i,j)$和$(i+1,j)$之间的门的颜色。

接下来一行一个整数$q$，表示询问数量。

接下来$q$行，第$i$行四个整数$a_{i}$，$b_{i}$，$c_{i}$，$d_{i}$表示询问是$(a_{i},b_{i})$到$(c_{i},d_{i})$路径上门的颜色个数的最小值。

输出格式

输出$q$行，每行一个整数表示这组询问的答案。

数据范围与提示

对于$100\%$的数据，$1 \leq n,m,q \leq 100$，$nm > 1$，$1 \leq a_{i},c_{i} \leq n$，$1 \leq b_{i},d_{i} \leq m$，$(a_{i},b_{i}) \neq (c_{i},d_{i})$，字符矩阵只有字符$P$，$C$，$Z$，$N$组成。

本题采用捆绑测试。

样例

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

4
2
3
1

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

2
2
1

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

1
2
1
3

说明

第一组询问，只需经过蓝色门；

第二组询问，只需经过蓝色门和绿色门；

第三组询问，只需经过蓝色门；

第四组询问，按图中的路径走，只需经过红色门、蓝色门、绿色门。