상자 밀기

베시와 친구들이 새 게임을 만들었다. 헛간은 $N \times M$ 격자다. 일부 칸에는 건초가 쌓여 있고, 베시는 그중 한 칸에 서 있으며 커다란 나무 상자가 다른 한 칸을 차지한다. 베시와 상자는 같은 칸에 동시에 있을 수 없고, 건초가 있는 칸에는 어느 쪽도 들어가지 못한다.

베시는 북, 동, 남, 서 네 방향으로 한 칸씩 움직인다. 건초가 있는 칸으로는 움직이지 못한다. 상자가 있는 칸으로 움직이려 하면 상자가 같은 방향으로 한 칸 밀린다. 밀려 갈 칸이 비어 있으면 상자가 그 칸으로 옮겨 가고 베시는 상자가 있던 칸으로 들어간다. 그 칸이 비어 있지 않으면 베시는 그 방향으로 움직이지 못한다.

헛간의 배치와 베시, 상자의 처음 위치가 주어진다. 목표 칸마다 처음 상태에서 시작해 상자를 그 칸까지 옮길 수 있는지 판정하라. 질의는 서로 독립이어서 모든 질의가 처음 상태에서 시작한다.

첫째 줄에 세 정수 $N$, $M$, $Q$가 주어진다. $N$은 격자의 행 개수, $M$은 열 개수, $Q$는 질의 개수다.

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

다음 $N$개의 줄에 격자가 한 줄씩 주어진다. 각 문자는 빈 칸을 뜻하는 ., 건초를 뜻하는 #, 베시의 시작 위치를 뜻하는 A, 상자의 처음 위치를 뜻하는 B 중 하나다. A와 B는 각각 정확히 한 번 나온다.

이어지는 $Q$개의 줄에 정수 쌍 $R$, $C$가 하나씩 주어진다. 맨 위 행이 1행이고 맨 왼쪽 열이 1열이며, $1 \le R \le N$, $1 \le C \le M$이다. 건초가 있는 칸이 질의로 주어지기도 한다.

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 쓴다. 상자를 그 칸으로 옮길 수 있으면 YES를, 그렇지 않으면 NO를 출력한다. 상자가 처음부터 놓여 있는 칸의 답은 YES다. 건초가 있는 칸의 답은 언제나 NO다.

예제에서 상자를 3행 5열로 옮기려면 베시가 오른쪽으로 세 칸 움직이면 된다. 나머지 세 질의는 베시가 어떻게 움직여도 상자를 그 칸에 놓지 못한다.