#216365. [NordicOI 2026] 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 pattern that repeats infinitely. See the figure below for exactly how this works.

:::align{center} :::

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 questions of the form: "If I teleport to cell , can I walk to cell ?"

The first line contains two integers and (), the number of rows and columns of the grid.

The next lines each contain a string of length , 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 (), the number of questions you must answer.

The following lines each contain four integers (), the coordinates of a question. It is guaranteed that neither of the cells at these coordinates is blocked.

For every question, print Yes if Harry can walk from cell to cell , otherwise print No.

样例输入 1

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

样例输出 1

Yes
No
Yes
Yes
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 and wants to move to . 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.