Беси и её друзья придумали новую игру "Затолкай ящик вокруг амбара в правый угол
не сдвигая сено".
Амбар может быть представлен прямоугольной решёткой \(N \times M\). В некоторых
ячейках решётки находится сено. Беси находится в одной ячейке этой решётки, а
большой деревянный ящик занимает другую. Беси и этот ящик не помещаются в одной
ячейке одновременно, также они не могут заходить в ячейку с сеном.
Бесси может двигаться в 4 ортогональных направлениях (север, юг, запад, восток).
пока не уткнётся в ячейку с сеном. Если она попытается войти в ячейку с ящиком,
то ящик продвинется на одну ячейку в этом же направлении, если там есть свободная
ячейка. Если свободной ячейки нет, Беси не может сдвинуть ящик.
Определённая ячейка решётки указана как цель. Беси должна доставить ящик в
это место.
По заданному описанию амбара, включая начальную позицию ящика и коровы, а также
целевую позицию ящика, определите можно ли победить в игре.
Замечание: в этой задаче можно использовать 512 Мбт оперативной памяти, в отличие
от лимита по умолчанию в 256 Мбт.
ФОРМАТ ВВОДА (файл pushabox.in):
Первая строка ввода содержит три числа \(N\), \(M\), \(Q\), где \(N\) - количество строк,
\(M\) - количество столбцов.
-
\(1 \le N,M \le 1500\).
-
\(1 \le Q \le 50,000\).
Следующие \(N\) строк описывают решётку, где символ '.' показывает пустую ячейку,
'#' - ячейку с сеном, 'A' - стартовую позицию Беси, 'B' - начальное положение ящика.
Далее следуют \(Q\) строк, каждая из которых содержит пару чисел \((R, C)\).
Для каждой пары Вы должны определить, возможно ли доставить ящик в эту ячейку,
со строкой \(R\), столбцом \(C\), из начального состояния амбара. Верхняя строка имеет
номер 1, левый столбец имеет номер 1.
ФОРМАТ ВЫВОДА (файл pushabox.out):
\(Q\) строк, каждая содержит одну из строк "YES" или "NO".
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 5 4
##.##
##.##
A.B..
##.##
##.##
3 2
3 5
1 3
5 3
|
NO
YES
NO
NO
|