Problem C
Backrooms

The wizard Harry likes to bake. One day, he found a spell that could transport him to the “backrooms” (this pun only works in Swedish), and he was filled with joy. However, when he used the spell, he was not transported to a bakery, but to an infinitely large grid. Each cell in the grid is either free or blocked. In the grid, you can move up, down, left, or right to adjacent cells that are not blocked. After walking around for a while, he notices that the pattern of blocked cells is periodic. More precisely, there is an $R \times C$ pattern that repeats infinitely. See the figure below for exactly how this works.

Figure 1: Visualization of Sample 1. The base pattern is marked in red. $(0,0)$ is not blocked, while $(1,1)$ is. The coordinates of the first question are drawn at $(2,4)$ and $(4,3)$. Naturally, the grid continues infinitely beyond what is drawn.

To escape, he needs to reach a certain cell in the grid. However, his teleportation magic is a bit rusty, so he will ask you $Q$ questions of the form: “If I teleport to cell $(s_x, s_y)$, can I walk to cell $(g_x, g_y)$?”

Input

The first line contains two integers $R$ and $C$ ($1 \leq R,C \leq 1000$), the number of rows and columns of the grid.

The next $R$ lines each contain a string of length $C$, consisting of the characters “.” and “#”. These are the rows of the grid. The character “#” means the cell is blocked, and “.” means the cell is free.

After that follows a line with the integer $Q$ ($1 \leq Q \leq 10^5$), the number of questions you must answer.

The following $Q$ lines each contain four integers $s_x, s_y, g_x, g_y$ ($0 \leq s_x, s_y, g_x, g_y \leq 10^{12}$), the coordinates of a question. It is guaranteed that neither of the cells at these coordinates is blocked.

Output

For every question, print “Yes” if Harry can walk from cell $(s_x, s_y)$ to cell $(g_x, g_y)$, otherwise print “No”.

Scoring

Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.

Explanation of Sample

• Question 1: Harry starts at $(2,4)$ and wants to move to $(4,3)$. To do this, he can move right, down and right.

• Question 2: the start and goal are separated by walls, so the answer is “No”.

• Question 3: Harry already starts at the goal, so he is done instantly.

• Question 4: even if we are very far out, the grid keeps going. The answer turns out to be “Yes”.

• Question 5: once again, the start and goal are separated by walls.

3 3
#.#
.#.
..#
5
2 4 4 3
0 0 2 1
0 0 0 0
900000002 900000004 900000004 900000003
2 1 1 2

Yes
No
Yes
Yes
No