Задача 38434. Game with chips

You are one of the developers of a new computer game. The game is played on a rectangular board consisting of W×H cells. Each cell can either contain or not contain a chip (see picture).
An important part of the game is to check if two pieces are connected in a way that satisfies the following properties:
1.    The path must consist of segments of vertical and horizontal straight lines.
2.    The path must not cross other tokens.
In this case, part of the path may be off the board. For example: Chips with coordinates (1, 3) and (4, 4) can be connected. Chips with coordinates (2, 3) and (5, 3) can also be connected. But chips with coordinates (2, 3) and (3, 4) cannot be connected — any path connecting them intersects other tiles.
You need to write a program that checks whether two tiles can be connected by a path that has the above properties, and, in case of a positive answer, determines the minimum length of such a path (it is assumed that the path has breaks, the beginning and end only in the centers of cells (or “ cells”, located outside the board), and the segment connecting the centers of two adjacent cells has a length of 1).

Input data format
The first line of the input file contains two natural numbers: W — board width, H — board height (1 ≤ W, H ≤ 75). The next H lines contain a description of the board: each line consists of exactly W characters: the character “X” (capital English letter “ex”) denotes a chip, the symbol “.” (dot) denotes an empty space. All other lines contain descriptions of requests: each request consists of four natural numbers separated by spaces — X₁, Y₁, X₂, Y₂, where 1 ≤ X₁, X₂ ≤ W, 1 ≤ Y₁, Y₂ ≤ H. Here (X₁, Y₁) and (X₂, Y₂) — the coordinates of the chips to be connected (the upper left cell has the coordinates (1, 1)). It is guaranteed that these coordinates will not match (except for the last request). The last line contains a query consisting of four numbers 0; this request does not need to be processed. The number of requests does not exceed 20.

Output data format
For each query, print one integer on a separate line — the length of the shortest path, or 0 if no such path exists.

Examples

#	Input	Output
1	5 4 XXXXX X...X XXX.X .XXX. 2 3 5 3 1 3 4 4 2 3 3 4 0 0 0 0	5 6 0
2	4 4 XXXX .X.. ..X. X... 1 1 3 1 0 0 0 0	4