What is an EJOI for you?

Game room!

Teo is searching for the Croatian EJOI team! She has already found Gabriel, but is still looking for Vito, Dino, and Ivo.

Teo and the EJOI team are in a labyrinth consisting of rooms, all the
same size. The rooms form a grid. The top-left room is labeled with , and
the bottom-right with . Between each pair of adjacent rooms, there is a door
colored in one of four colors: blue (marked with `P`

), red (marked with `C`

), green (marked with `Z`

) and
orange (marked with `N`

).

Illustration of the third example. The black circle marks the room in which Teo and Gabriel are located in the fourth question, and the white circle marks the room in which Vito, Ivo and Dino are located. The gray path is one of the possible paths that passes through three different door colors.

At some point, Gabriel says:

I know where the rest of the team is, but I will only tell you if you can answer all of my questions.

Gabriel's questions are:

If we are currently in room and the rest of the team is in room , what is the minimum number of door colors we have to go through to reach them?

Teo is very good at answering Gabriel's questions, but there are simply too many of them. She does not have much time (the bus is leaving soon), so she is asking you to help her answer of Gabriel's questions!

#### Input Specification

The first line contains integers and , the number of rooms.

The -th of the following lines contains characters (`P`

, `C`

, `Z`

or `N`

), where the -th character
marks the colour of the door that connects rooms and (.

The -th of the following lines contains characters (`P`

, `C`

, `Z`

or `N`

), where the -th character
marks the colour of the door that connects rooms and .

The next line contains the integer , the number of Gabriel's questions.

In the -th of the following lines, there are four integers , , , , the description of Gabriel's -th question.

#### Output Specification

In the -th of lines, output the answer to Gabriel's -th question.

#### Constraints

Subtask | Points | Constraints |
---|---|---|

1 | 11 | |

2 | 13 | All doors that connect rooms with are blue, and all doors that connect rooms with are red. |

3 | 24 | Every door is either red or blue. |

4 | 22 | No additional constraints. |

#### Sample Input 1

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

#### Sample Output 1

```
4
2
3
1
```

#### Sample Input 2

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

#### Sample Output 2

```
2
2
1
```

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

#### Sample Output 3

```
1
2
1
3
```

#### Explanation for Sample 3

The third example is illustrated in the problem statement.

For the first question, Teo and Gabriel can use just the blue doors to reach the rest of the team; for the second question, they can use blue and green doors; for the third, again, only blue is enough; and for the fourth, they can use blue, green, and red doors.

## Comments