Escape the Labyrinth

An infinite labyrinth is formed by tiling the entire plane with a rectangular pattern of size \(n \times m\). Each cell of the pattern is either empty (denoted by '.') or blocked (denoted by '#'). The tiling is done without any rotations or reflections, so that for any cell with coordinates \( (r, c) \) (where \(r\) and \(c\) are integers and the origin is \( (0,0) \)), the cell is empty if and only if the cell at coordinates \((r \bmod n, c \bmod m)\) in the pattern is empty.

You are given the pattern and a list of \(q\) queries. In each query you are given a starting cell \( (x, y) \) in the infinite grid. From the starting cell you can move to an adjacent cell (up, down, left or right) provided that the destination cell is empty; moves are allowed only between adjacent cells (no diagonal moves).

You need to decide whether it is possible to reach the origin \( (0,0) \) from the starting cell by moving only through empty cells. Note that the labyrinth is infinite and periodic. Formally, if we write \(x = a\,n + i\) and \(y = b\,m + j\), where \(0 \le i < n\) and \(0 \le j < m\), then the starting cell is the copy of cell \((i,j)\) with offset \((a,b)\). Let a potential (or offset) be introduced while moving between copies. When moving from a cell at pattern coordinate \((i, j)\) to a neighboring cell at \((i+\Delta i, j+\Delta j)\), we define the shift as follows:

\[ \text{new_row} = (i+\Delta i) \bmod n, \quad s_r = \begin{cases} 0, & \text{if }0 \le i+\Delta i < n,\\ 1, & \text{if } i+\Delta i \ge n,\\ -1, & \text{if } i+\Delta i < 0,\end{cases} \] \[ \text{new_col} = (j+\Delta j) \bmod m, \quad s_c = \begin{cases} 0, & \text{if }0 \le j+\Delta j < m,\\ 1, & \text{if } j+\Delta j \ge m,\\ -1, & \text{if } j+\Delta j < 0.\end{cases} \]

If there exists a path from the starting cell \((i, j)\) with copy offset \( (a, b) \) to the origin \((0,0)\) such that the sum of all shifts equals \((-a, -b)\), then the labyrinth can be escaped. Due to the periodicity, similar cells on the base pattern are connected in a lifted graph where cycles may allow adjustments of the overall translation. In particular, if the connected component (on the torus induced by the pattern) that contains the origin has a nonzero cycle translation (i.e. a cycle whose net shift is nonzero), then many different offsets can be achieved. Otherwise, if all cycles have zero net shift, the potential (or offset) is uniquely determined for every cell in the component.

Your task is to determine for each query whether escaping (i.e. reaching the origin \((0,0)\)) is possible.

inputFormat

The first line contains two integers \(n\) and \(m\) (pattern dimensions).

The following \(n\) lines each contain a string of length \(m\) consisting only of characters . (empty) and # (blocked).

The next line contains an integer \(q\) denoting the number of queries.

Each of the next \(q\) lines contains two integers \(x\) and \(y\) representing the coordinates of a starting cell.

outputFormat

For each query, output a single line containing YES if it is possible to reach the origin \((0,0)\) and NO otherwise.

sample

2 2
.#
..
3
0 0
0 1
3 2

YES
NO
NO