Problem B
Babel

Photo retrieved from wikipedia.org. Image Source

The Tower of Babel is a biblical story in Genesis in which the entire world had one language and a common speech. Of course, the moment the entire world could easily communicate they decided to build a tower that would reach to the heavens so they would not be “scattered over the face of the earth.” God, however, did not allow the people to build this tower, and He stopped this by “confusing their language” so that they no longer had one common language.

After this scattering, a person only knew a single language and cross-cultural communication was impossible. Thus, it became vital for the people to know if they could travel from place to place without moving through an area where an unknown language was spoken. One day, when God was feeling particularly gracious, he published a map with the locations where each language was spoken. For example:

EEEE
FFFG
FGGG
FFAA
AAFA

Each letter represents a common language (in the example above, E = English, F = French, A = Arabic, G = Greek). Language areas are considered connected if any of the four adjacent areas (north, south, east, or west) speak the same language.

Given the map and $q$ pairs of coordinates, can you determine if an individual can move between the two coordinates without passing through an area that speaks another language?

Input

The first line of input contains two integers, $1 \leq R \leq 1\, 000$, denoting the number of rows in the map, and $1 \leq C \leq 1\, 000$, denoting the number of columns in the map. The following $R$ lines contain exactly $C$ characters, all of which will be uppercase letters of the alphabet A-Z not including N. The next line contains an integer $0 \leq Q \leq 1\, 000$, indicating the number of queries to follow. The following $Q$ lines each contain one query, given as four space separated integers $r_1, c_1, r_2, c_2$ such that $0 \leq r_1, r_2 < R, 0 \leq c_1, c_2 < C$. $r_1$ and $c_1$ are the row and column on the map from where the person is trying to travel, and $r_2$ and $c_2$ are the row and column on the map where the person is trying to travel to.

Output

For each query, output the character of the language that connects the two points without passing through an area that speaks another language. If it is not possible for any language to do this, output the letter “N”.

5 4
EEEE
FFFG
FGGG
FFAA
AAFA
5
0 0 0 1
4 0 4 3
1 0 1 2
1 0 2 0
3 1 4 2

E
N
F
F
N

10 10
ABABABABAB
BABABABABA
AAAAAAAABA
BBBBBBBBBA
AAAAAAAAAA
CCCCCCCAAA
CDDDDDDDDA
CDDDDDDDAA
AAAAAAAAAA
ADDDDDDDDD
10
0 0 0 1
0 0 0 2
0 1 0 3
0 0 1 1
1 9 9 0
1 9 2 0
1 8 3 0
6 8 7 7
9 9 9 1
0 9 1 8

N
N
N
N
A
N
B
D
D
N