Turning Turtles#4350
Military built a rectangular training ground of w \times 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 degrees. So the complexity of the route is calculated 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 and , the lengths of the ground sides (1 \leq w \cdot h \leq 100000). Then follows the map of the polygon — lines with symbols in each. Symbol "#" stands for a passable cell and "." stands for a non-passable cell. Line number (h+2) contains an integer , the number of routes you have to calculate the complexity for (1 \leq q \leq 50000). Each of the next 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 to from top to bottom, columns are numerated to from left to right.
For each route output its complexity in a separate line.
Example 1