Đẩy Hộp

Bessie đang ở trong một cái kho hình chữ nhật kích thước $N\times M$ ô vuông. Mỗi ô có thể là ô trống (.), chướng ngại vật (#), vị trí của Bessie (A), hoặc vị trí của hộp (B). Bessie có thể di chuyển lên, xuống, trái, phải sang các ô trống liền kề (không phải chướng ngại vật và không phải ô chứa hộp).

Khi Bessie di chuyển vào ô chứa hộp, cô sẽ đẩy hộp theo cùng hướng đó — hộp dịch chuyển sang ô tiếp theo theo hướng di chuyển của Bessie. Nếu ô tiếp theo của hộp là chướng ngại vật hoặc nằm ngoài biên, việc đẩy không hợp lệ và Bessie không thể thực hiện bước đó.

Cho $Q$ truy vấn, mỗi truy vấn hỏi: Bessie có thể đẩy hộp đến ô $(r,c)$ hay không?

Dữ liệu vào

• Dòng đầu: ba số nguyên $N$, $M$, $Q$.
• $N$ dòng tiếp theo: mô tả lưới kho, mỗi dòng gồm $M$ ký tự (#, ., A, B).
• $Q$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $r$, $c$ — tọa độ ô đích (1-indexed).

Dữ liệu ra

Với mỗi truy vấn, in YES nếu Bessie có thể đẩy hộp đến ô $(r,c)$, ngược lại in NO.

Ràng buộc

• $1\le N,M\le 1500$
• $1\le Q\le {10}^5$
• Đúng một ô là A và đúng một ô là B.
• Ô đích $(r,c)$ của mỗi truy vấn luôn là ô trống hoặc ô B.

Ví dụ

Ghi chú

Đây là bài toán từ USACO December 2017 Platinum, Problem 2.