E. Быстрая Черепаха
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
stdin
вывод
stdout

У Джона Доу есть поле, представляющее собой прямоугольную таблицу размера n × m. Будем считать, что строки поля пронумерованы от 1 до n сверху вниз, а столбцы поля от 1 до m слева направо. Тогда клетка поля, стоящая на пересечении x-ой строки y-го столбца, имеет координаты (x; y).

Известно, что некоторые клетки поля Джона покрашены в белый, а некоторые — в черный цвет. Так же у Джона есть черепаха, которая может двигаться по белым клеткам поля. Из белой клетки с координатами (x; y) черепаха Джона может попасть в клетку (x + 1; y) или (x; y + 1), если соответствующая клетка покрашена в белый цвет. Другими словами, черепаха может ходить только белым клеткам поля вправо или вниз. Черепаха не может выходить за пределы поля.

В добавок ко всему у Джона есть q запросов, каждый из которых характеризуется четырьмя числами x1, y1, x2, y2 (x1 ≤ x2, y1 ≤ y2). Для каждого запроса Джон хочет узнать, сможет ли черепаха, стартовав в клетке c координатами (x1; y1), дойти до клетки с координатами (x2; y2), двигаясь только по белым клеткам поля.

Входные данные

В первой строке через пробел записаны два целых числа n и m (1 ≤ n, m ≤ 500) — размеры поля.

В следующих n строках содержится по m символов «#» и «.»: j-ый символ i-ой из этих строк равен «#», если клетка (i; j) покрашена в черный цвет и «.», если в белый.

В следующей строке записано целое число q (1 ≤ q ≤ 6·105) — количество запросов. В следующих q строках через пробел записаны четыре целых числа x1, y1, x2 и y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — координаты стартовой и конечной клетки. Гарантируется, что клетки (x1; y1) и (x2; y2) белые.

Выходные данные

Для каждого из q запросов выведите в отдельной строке «Yes», если существует путь из клетки (x1; y1) в клетку (x2; y2), отвечающий требованиям, и «No» в противном случае. Ответы на запросы выводите в том порядке, в котором запросы заданы во входных данных.

Примеры
Входные данные
3 3
...
.##
.#.
5
1 1 3 3
1 1 1 3
1 1 3 1
1 1 1 2
1 1 2 1
Выходные данные
No
Yes
Yes
Yes
Yes
Входные данные
5 5
.....
.###.
.....
.###.
.....
5
1 1 5 5
1 1 1 5
1 1 3 4
2 1 2 5
1 1 2 5
Выходные данные
Yes
Yes
Yes
No
Yes