10 Kinds of People – Kattis, Kattis (original) (raw)

Hide

The world is made up of 101010 kinds of people, those who understand binary and those who do not. These different kinds of people do not always get along so well. Bob might ask for a$10000$ ounce coffee (meaning binary) and Alice might make misinterpret his request as being in decimal and give him a 100111000100001001110001000010011100010000 ounce coffee (binary). After Sue explains that this much coffee costs$100$ dollars (decimal), Bob might assume he only has to pay 444 dollars (interpreting the price as being in binary). In response to these differences that are difficult to resolve, these two groups have divided the world into two regions, the binary-friendly zones and the decimal-friendly zones. They have even published a map like the following to help people keep up with where the areas are (they have used ones and zeros so nobody would have trouble reading it).

1111100000
1111000000
1110000011
0111100111
0011111111

Users of binary have to stay in the zones marked with a zero. Users of decimal have to stay in the zones marked with a one. You have to figure out if it is possible for either type of person to get between various locations of interest. People can move north, south, east or west, but cannot move diagonally.

Input

Input starts with a line containing two positive integers,$1 \le r \le 1\, 000$ and$1 \le c \le 1\, 000$. The next rrr input lines give the contents of the map, each line containing exactly$c$ characters (which are all chosen from 000 or$1$).

The next line has an integer 0lenle1,0000 \le n \le 1\, 0000lenle1,000. The following$n$ lines each contain one query, given as four integers: r1,c1r_1,c_1r1,c1 and r2,c2r_2,c_2r2,c2. These two pairs indicate two locations on the map, and their limits are 1ler1,r2ler1 \le r_1, r_2 \le r1ler_1,r_2ler and$1 \le c_1, c_2 \le c$.

Output

For each query, output binary if a binary user can start from location r1,c1r_1, c_1r_1,c_1 and move to location$r_2, c_2$. Outputdecimal if a decimal user can move between the two locations. Otherwise, output neither.

Please log in to submit a solution to this problem

Log in

You haven't made any submissions on this problem yet.