Background

Teo and the Croatian EJOI team are inside a maze.

Problem Description

The maze is an $n \times m$ grid. The top-left cell is $(1,1)$, and the bottom-right cell is $(n,m)$. Between every pair of adjacent cells (4-neighborhood, i.e., adjacent up, down, left, right), there is a door. Doors have four colors: blue, red, green, and orange, represented by the characters P, C, Z, N, respectively. You can only move to other cells by passing through doors.

Now Teo gives you $q$ queries. Each query provides $a,b,c,d$, asking you to find a path from $(a,b)$ to $(c,d)$ that minimizes the number of distinct door colors used along the path. You need to output this minimum number of colors.

Input Format

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

Next is a character matrix with $n$ rows and $m - 1$ columns. The character in row $i$, column $j$ represents the color of the door between $(i,j)$ and $(i,j+1)$.

Next is a character matrix with $n - 1$ rows and $m$ columns. The character in row $i$, column $j$ represents the color of the door between $(i,j)$ and $(i+1,j)$.

Next is one line with an integer $q$, representing the number of queries.

Then follow $q$ lines. The $i$-th line contains four integers $a_i, b_i, c_i, d_i$, meaning the minimum number of distinct door colors on a path from $(a_i,b_i)$ to $(c_i,d_i)$.

Output Format

Output $q$ lines, each containing one integer, which is the answer to the corresponding query.

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

Hint

Sample Explanation #3

As shown in the figure.

• For the first query, you only need to pass through blue doors.
• For the second query, you only need to pass through blue and green doors.
• For the third query, you only need to pass through blue doors.
• For the fourth query, following the path in the figure, you only need to pass through red, blue, and green doors.

Constraints

For $100\%$ of the testdata, $1 \le n,m,q \le 100$, $nm > 1$, $1 \le a_i,c_i \le n$, $1 \le b_i,d_i \le m$, $(a_i,b_i) \ne (c_i,d_i)$, and the character matrices consist only of the characters P, C, Z, N.

This problem uses bundled tests.

Notes

The scoring of this problem follows the original COCI problem settings, with a full score of $70$.

Translated from COCI2023-2024 CONTEST #1 T2 Labirint.

Translated by ChatGPT 5