Grid Path Existence

You are given a grid with N rows and M columns. Each cell of the grid is either . (free cell) or # (obstacle). You need to answer Q queries. In each query, you are given two pairs of coordinates: the starting cell and the destination cell. The task is to determine whether there is a path from the starting cell to the destination cell moving only up, down, left, or right without passing through obstacles.

The problem can be formulated as follows:

Given a grid \(G\) of size \(N \times M\) where each cell \(G_{i,j}\) is either \('.'\) or \('#'\), and given a query with start cell \((x_1, y_1)\) and target cell \((x_2, y_2)\) (with coordinates 1-indexed), determine whether there exists a path from \((x_1, y_1)\) to \((x_2, y_2)\) such that each step moves in one of the four cardinal directions and only passes through cells containing ..

The solution is expected to use a breadth-first search (BFS) algorithm. The time complexity of BFS is \(O(N \times M)\), which is efficient for grids of moderate size.

inputFormat

The input is given from stdin in the following format:

N M
row1
row2
... 
rowN
Q
x1 y1 x2 y2
x1 y1 x2 y2
... (Q queries)

Where:

• N and M are the numbers of rows and columns in the grid respectively.
• Each of the next N lines contains a string of length M representing a row of the grid.
• Q is the number of queries.
• Each query consists of four integers: the row and column of the start cell and the row and column of the destination cell. Note that the coordinates are 1-indexed.

outputFormat

For each query, output a single line to stdout with either YES if there exists a path between the given start and destination cells, or NO if there does not exist such a path.

## sample

4 4
....
.#..
....
...#
2
1 1 3 3
1 1 4 4

YES
NO

</p>