题目描述

题目译自 USACO 2017 December Contest, Platinum Problem 2. Push a Box

一个谷仓是一个 $N \times M$ 的矩形网格，有一些网格里有干草。 Bessie 站在其中一个格子内，还有一个格子里有一个大木箱。 Bessie 不能和大木箱在一个格子里，也不能和干草在一个格子里。

如果她不与干草在同一个格子，她就可以往自己旁边的四个方向（东西南北）移动，如果她想移动到有木箱的格子里，那个木箱就会被她推一格（只要木箱的那个方向还有空间），如果没有空间，那 Bessie 就不能移动了。

给你谷仓的布局（空格子，干草以及木箱位置）以及 Bessie 的出发位置和箱子要被推到的位置，请你帮忙计算 Bessie 能不能把木箱推到指定位置。

输入格式

第一行有三个数 $N,M,Q$，其中 $N$ 是谷仓的行数，$M$ 是列数，$Q$ 是询问数。

接下来 $N$ 行是谷仓的初始布局，其中 . 代表空格子， # 代表干草格子， A 代表 Bessie 的初始位置， B 是木箱的初始位置。

接下来 $Q$ 行，每行一个坐标 $(R,C)$ ，代表第 $R$ 行第 $C$ 行。对于每行，你要输出 Bessie 是否有可能把箱子推到这个位置。

输出格式

$Q$ 行，每行一个答案，如果 Bessie 能走到，输出 YES ，否则输出 NO 。

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

NO
YES
NO
NO

提示

对于 $100\%$ 的数据，保证 $1\leq N,M \leq 1500$，$1\leq Q\leq 50000$。