Push a Box

Bessie and her friends invented a new game. The barn is an $N \times M$ rectangular grid. Some cells hold hay. Bessie stands on one cell and a large wooden box sits on another. Bessie and the box cannot be on the same cell at the same time, and neither of them can enter a cell that holds hay.

Bessie moves one cell at a time in the four orthogonal directions (north, east, south, west). She never walks into hay. If she tries to move onto the cell with the box, the box is pushed one cell in the same direction. If the cell behind the box is empty, the box moves there and Bessie steps onto the cell the box just left. If that cell is not empty, Bessie cannot make the move.

You are given the layout of the barn with the starting positions of Bessie and the box. For each target cell, decide whether the box can be brought to that cell starting from the initial state of the barn. The queries are independent, so every query starts from the initial state.

The first line has three integers $N$, $M$, and $Q$, where $N$ is the number of rows of the grid, $M$ is the number of columns, and $Q$ is the number of queries.

• $1 \le N, M \le 1500$
• $1 \le Q \le 50000$

Each of the next $N$ lines holds one row of the grid. Every character is one of these: . for an empty cell, # for hay, A for Bessie's starting position, and B for the box's initial location. A and B each appear exactly once.

Each of the following $Q$ lines has a pair of integers $R$ and $C$. The top row is row 1 and the left column is column 1, so $1 \le R \le N$ and $1 \le C \le M$. A query may name a cell that holds hay.

Print $Q$ lines. Line $i$ holds the answer to query $i$: YES if the box can be brought to that cell, and NO otherwise. The cell where the box starts answers YES. A cell with hay always answers NO.

In the example, pushing the box to row 3, column 5 takes three moves to the right. The other three cells cannot be reached by any sequence of moves.