Problem Background

Teo and the Croatian EJOI team are inside a labyrinth.

Problem Description

The labyrinth is an $n \times m$ grid, with coordinates $(1,1)$ representing the top-left cell and coordinates $(n,m)$ representing the bottom-right cell. Each pair of adjacent (four-connected, i.e., adjacent to the top, bottom, left, or right) cells has a door. These doors come in four colors: blue, red, green, and orange, represented by the characters P, C, Z, and N, respectively. Movement between cells is only possible through these doors.

Teo will give you $q$ queries. Each query specifies $a, b, c, d$, asking for the shortest path from $(a, b)$ to $(c, d)$ while minimizing the number of distinct door colors passed through. You are to answer the minimum number of distinct colors required.

Input Format

The first line contains two integers $n$ and $m$, representing the number of rows and columns of the grid.

The next $n$ lines, each with $m-1$ characters, describe the horizontal doors between cells $(i, j)$ and $(i, j+1)$.

The following $n-1$ lines, each with $m$ characters, describe the vertical doors between cells $(i, j)$ and $(i+1, j)$.

The next line contains an integer $q$, the number of queries.

The following $q$ lines each contain four integers $a_i, b_i, c_i, d_i$, representing the query for the minimum number of distinct door colors from $(a_i, b_i)$ to $(c_i, d_i)$.

Output Format

Output $q$ lines, each containing a single integer representing the answer to the corresponding query.

Sample Input and Output

Input Sample #1

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

Output Sample #1

4
2
3
1

Input Sample #2

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

Output Sample #2

2
2
1

Input Sample #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

Output Sample #3

1
2
1
3

Notes

Sample Explanation #3

As illustrated in the figure:

• For the first query, only blue doors need to be passed through.
• For the second query, both blue and green doors need to be passed through.
• For the third query, only blue doors need to be passed through.
• For the fourth query, the path includes red, blue, and green doors.

Data Range

For $100\%$ of the data, $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)$, and the character matrices only contain the characters P, C, Z, and N.

This problem uses subtask testing.

Notes

This problem's score is set according to the original COCI contest, with a maximum of 70 points.

The problem is translated from COCI2022-2023 CONTEST #1 T2 Labyrinth.

见题面 Input 部分

见题面 Output 部分