Штовхни коробку

Бессі та її друзі вигадали нову гру "Заштовхай ящик у правий кут комори, не зрушуючи сіно". Комора представлена у вигляді прямокутної сітки розміром n на m. Деякі клітинки цієї сітки зайняті сіном. Бессі знаходиться в одній з клітинок, а великий дерев'яний ящик — в іншій. Бессі та ящик не можуть перебувати в одній клітинці одночасно, і вони не можуть заходити в клітинки, зайняті сіном.

Бессі може рухатися в 4 ортогональних напрямках (північ, південь, захід, схід), поки не натрапить на клітинку з сіном. Якщо вона намагається увійти в клітинку з ящиком, то ящик зсувається на одну клітинку в тому ж напрямку, якщо ця клітинка вільна. Якщо вільної клітинки немає, Бессі не може зрушити ящик.

Одна з клітинок сітки визначена як ціль. Завдання Бессі — доставити ящик у цю клітинку.

За заданим описом комори, включаючи початкові позиції ящика та корови, а також цільову позицію ящика, визначте, чи можна виграти в цій грі.

Вхідні дані

Перша стрічка вводу містить три числа: n, m (1 ≤ n, m ≤ 1500), q (1 ≤ q ≤ 50000), де n — кількість рядків, m — кількість стовпців.

Наступні n рядків описують сітку, де символ '.' позначає порожню клітинку, '#' — клітинку з сіном, 'A' — стартову позицію Бессі, 'B' — початкове положення ящика.

Далі йдуть q рядків, кожен з яких містить пару чисел (r, c). Для кожної пари ви повинні визначити, чи можливо доставити ящик у цю клітинку з рядком r і стовпцем c, починаючи з початкового стану комори. Верхній рядок має номер 1, лівий стовпець має номер 1.

Вихідні дані

Виведіть q рядків, кожен з яких містить або "YES", або "NO".

Приклади

Примітка

Щоб перемістити ящик у позицію (3, 5), корова повинна зробити 3 кроки вправо.

Усі інші позиції недосяжні.