Bessie và những người bạn đã phát minh ra một trò chơi mới. Tên trò chơi mô tả rất chính xác, dù không mấy sáng tạo. Chúng gọi trò chơi là “Đẩy một chiếc hộp quanh chuồng để đưa nó vào đúng vị trí và đừng làm xê dịch cỏ khô” (nếu bạn thấy cái tên này quá dài, bạn nên xem thử tên một số biến mà những cô bò dùng khi viết mã...)

Chuồng bò có thể được mô hình hóa thành một lưới chữ nhật \(N \times M\). Một số ô của lưới có cỏ khô. Bessie đứng ở một ô trong lưới và một chiếc hộp gỗ lớn nằm ở một ô khác. Bessie và chiếc hộp không thể cùng nằm trong một ô, đồng thời cả hai đều không thể nằm trong ô chứa cỏ khô.

Bessie có thể di chuyển theo bốn hướng trực giao (bắc, đông, nam, tây), miễn là cô không đi vào cỏ khô. Nếu cô cố bước vào ô đang có chiếc hộp, chiếc hộp sẽ bị đẩy một ô theo hướng đó, với điều kiện phía bên kia có một ô trống. Nếu không có ô trống, Bessie không thể thực hiện bước di chuyển ấy.

Một ô nhất định trên lưới được chọn làm đích. Mục tiêu của Bessie là đưa chiếc hộp vào vị trí đó.

Cho sơ đồ chuồng bò, bao gồm vị trí ban đầu của chiếc hộp, vị trí ban đầu của Bessie và vị trí đích của chiếc hộp, hãy xác định liệu có thể thắng trò chơi hay không.

Lưu ý: Bài toán này cho phép sử dụng \(512\) MB bộ nhớ, tăng so với giới hạn mặc định \(256\) MB.

Dữ liệu vào

Dòng đầu tiên chứa ba số \(N\), \(M\) và \(Q\), trong đó \(N\) là số hàng và \(M\) là số cột của lưới.

• \(1 \leq N, M \leq 1500\).
• \(1 \leq Q \leq 50{,}000\).

\(N\) dòng tiếp theo biểu diễn lưới. Các ký tự lần lượt biểu thị ô trống (.), cỏ khô (#), vị trí ban đầu của Bessie (A) và vị trí ban đầu của chiếc hộp (B).

Sau đó là \(Q\) dòng, mỗi dòng chứa một cặp số nguyên \((R, C)\). Với mỗi cặp, hãy xác định liệu có thể đưa chiếc hộp đến ô ở hàng \(R\), cột \(C\) từ trạng thái ban đầu của chuồng hay không. Hàng trên cùng là hàng \(1\) và cột bên trái là cột \(1\).

Dữ liệu ra

In ra \(Q\) dòng, mỗi dòng chứa chuỗi YES hoặc NO.

Ví dụ

5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3

NO
YES
NO
NO

Nguồn

USACO 2017 December Contest, Platinum — Push a Box

Tác giả bài toán: Nathan Pinsker.