ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1699. Turning Turtles

Time limit: 2.0 second
Memory limit: 64 MB
Military built a rectangular training ground of w × h cells to train battle turtles. Some of the cells are passable for turtles, and some of them are not. Turtles can move only parallel to the sides of the training ground. The ground is constructed in such a way that there is exactly one way to get from one passable cell to another passable cell without visiting any cell twice. It is known that turtles can run very fast along a straight line, but it is difficult for them to turn 90 degrees. So the complexity of the route is caluclated as the number of turns the turtle will make on its way from the initial to the final cell of the route. Your task is to write a program which will calculate the complexity of the route knowing its initial and final cell.


The first line contains two space-separated integers h and w, the lengths of the ground sides (1 ≤ w · h ≤ 100000). Then follows the map of the polygon—h lines with w symbols in each. Symbol “#” stays for a passable cell and “.” stays for a non-passable cell. Line number h + 2 contains an integer q, the number of routes you have to calculate the complexity for (1 ≤ q ≤ 50000). Each of the next q lines contains four space-separated integers: the number of row and the number of column of the initial cell of the route, the number of row and the number of column of the final cell of the route, respectively. It is guaranteed that the initial and the final cells of the route are passable. Rows are numerated 1 to h from top to bottom, columns are numerated 1 to w from left to right.


For each route output its complexity in a separate line.


5 4
1 2 2 1
2 3 4 3
4 2 3 4
1 2 4 2
Problem Author: Alex Samsonov
Problem Source: Ural SU Contest. Petrozavodsk Winter Session, February 2009