Maze Paths with Minimum Distinct Door Colors

The maze is represented by an \(n \times m\) grid. Each cell is identified by its coordinates \((i,j)\) with \((1,1)\) being the top-left corner and \((n,m)\) the bottom-right corner. Between every pair of adjacent cells (in the four cardinal directions), there is a door. Each door is painted in one of four colors: blue, red, green, or orange, denoted by the characters P, C, Z, and N respectively. You can only move between cells by passing through these doors.

You are given the structure of the maze as follows. First, you are given three integers \(n\), \(m\) and \(q\), where \(n\) and \(m\) denote the number of rows and columns of the grid, and \(q\) is the number of queries. Then:

• Next \(n\) lines each contain a string of length \(m-1\) representing the colors of the horizontal doors. The \(j\)-th character in the \(i\)-th line denotes the door between cell \((i, j)\) and \((i, j+1)\).
• Next \(n-1\) lines each contain a string of length \(m\) representing the colors of the vertical doors. The \(j\)-th character in the \(i\)-th line denotes the door between cell \((i, j)\) and \((i+1, j)\).

Each of the following \(q\) lines contains four integers \(a\), \(b\), \(c\), \(d\). For each query, you are to find a path from cell \((a, b)\) to cell \((c, d)\) that minimizes the number of distinct door colors encountered along the path, and output that minimum number.

Note: When you use a door color more than once on the same path, it is only counted once.

inputFormat

The input is given in the following format:

 n m q
 (next n lines): each line is a string of length m-1 indicating horizontal door colors
 (next n-1 lines): each line is a string of length m indicating vertical door colors
 (next q lines): each line contains four integers a, b, c, d

Here, \(1 \leq a, c \leq n\) and \(1 \leq b, d \leq m\).

outputFormat

For each query, output a single integer representing the minimum number of distinct door colors encountered along any valid path from \((a, b)\) to \((c, d)\).

sample

3 3 3
PC
ZP
CN
PZC
NCP
1 1 3 3
1 2 2 2
3 1 3 3

2
1
2