J. Доставка в городе будущего
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Город будущего — идеальный прямоугольник разбитый на $$$n \times m$$$ единичных квадратиков, в каждом из которых расположено здание. Для упрощения схемы города, названия зданий на ней сокращены до одной первой буквы.

Транспорт будущего достаточно быстрый и позволяет произвести мгновенный перелет от здания к зданию, если удовлетворены следующие особенности:

  • Эти здания находятся в одной строке или столбце схемы.
  • Названия этих зданий совпадают по первой букве.
  • На пути между этими зданиями есть хотя бы еще одно здание, которое также совпадает по первой букве названия.

Например: abbba — невозможно, так как не выполняется 3-й пункт, ababa — возможно, так как есть еще одно здание a.

Доставка будущего — совершенно новый сервис, который пользуется транспортом будущего в городе будущего и доставляет пиццу будущего. Вам поручено произвести последнюю доработку в интеллектуальной системе доставки будущего — проверку зоны доставки клиента. Так, вам будет дано $$$q$$$ запросов «$$$x_1,y_1,x_2,y_2$$$», а вы, пожалуйста, проверьте, возможно ли мгновенно доставить пиццу транспортом будущего от здания «$$$x_1,y_1$$$» к зданию «$$$x_2,y_2$$$». Мгновенная доставка может осуществляться с помощью нескольких мгновенных переходов.

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

В первой строке входного файла содержатся два целых числа $$$n, m$$$ — размеры схемы.

Каждая из последующих $$$n$$$ строк содержит $$$m$$$ маленьких букв латинского алфавита — первые буквы названий зданий.

Следующая строка содержит одно целое число $$$q$$$ — количество запросов.

Каждая из последующих $$$q$$$ строка содержит $$$4$$$ разделенных пробелом целых числа $$$x_1,y_1,x_2,y_2$$$ — параметры запроса.

$$$$$$1 \le n, m \le 1000$$$$$$ $$$$$$1 \le q \le 10^6$$$$$$ $$$$$$1 \le x_1, x_2 \le n$$$$$$ $$$$$$1 \le y_1, y_2 \le m$$$$$$

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

Выведите $$$q$$$ строк, $$$i$$$-я из которых «Yes» или «No» — возможно ли доставить пиццу в $$$i$$$-м запросе.

Пример
Входные данные
3 3
aaa
aaa
aaa
5
1 1 1 2
2 2 1 1
2 2 1 2
3 3 1 1
3 2 1 2
Выходные данные
No
No
No
Yes
Yes
Примечание

В первом примере все здания имеют одну и ту же первую букву в названии, однако доставить пиццу транспортом будущего не всегда возможно.