Иван почти доделал ремонт в ванной комнате. Хотя, если говорить честно, пока что он успел только положить плитку на пол. Узор каждой плитки представляет собой клетчатое поле размера $$$h \times w$$$. Каждая клетка окрашена в чёрный или белый цвет. Пол в ванной Ивана устроен таким образом, что в него уместилось ровно $$$n$$$ плиток, образовав клетчатое поле размера $$$h \times nw$$$.
Рассмотрим это клетчатое поле сверху: пронумеруем строки сверху вниз числами от $$$1$$$ до $$$h$$$, а столбцы слева направо числами от $$$1$$$ до $$$nw$$$. Координатами клетки будем считать два числа $$$(r, c)$$$, где $$$r$$$ — номер строки, а $$$c$$$ — номер столбца.
Так как в рамках ремонта Иван сделал только плитку, ему стало грустно, и он решил развлечься. Он $$$q$$$ раз выбрал две белые клетки, расположенные в клетках с координатами $$$(r_1, c_1)$$$ и $$$(r_2, c_2)$$$. Для каждой выбранной пары клеток он хочет узнать, существует ли путь из первой во вторую, проходящий строго по белым клеткам. Соседние клетки в пути должны иметь общую сторону. При этом есть очень важное условие, что зазор между двумя плитками можно пересекать строго в направлении слева направо. В пределах одной плитки можно двигаться по белым клеткам в любом направлении.
Помогите Ивану ответить на все запросы. Гарантируется, что все клетки, данные в запросах, окрашены в белый цвет.
В первой строке входных данных содержится три целых числа $$$h$$$, $$$w$$$, $$$n$$$ ($$$1 \leq h, w \leq 250$$$, $$$1 \leq n \leq 10^9$$$) — высоту, ширину узора плитки и количество плиток.
В следующих $$$h$$$ строках входных данных описывается узор плитки. Каждая из этих $$$h$$$ строк содержит $$$w$$$ символов. В $$$r$$$-й строке $$$c$$$-й символ равен «0», если клетка с координатами $$$(r, c)$$$ является чёрной, и «1» — если белой.
В следующей строке входных данных содержится одно целое число $$$q$$$ ($$$1 \leq q \leq 10^6$$$) — количество запросов.
В следующих $$$q$$$ строках входных данных описываются запросы — четыре целых числа $$$r_1$$$, $$$c_1$$$, $$$r_2$$$ и $$$c_2$$$ ($$$1 \leq r_1, r_2 \leq h$$$, $$$1 \leq c_1, c_2 \leq nw$$$).
Гарантируется, что все клетки $$$(r_1, c_1)$$$ и все клетки $$$(r_2, c_2)$$$ окрашены в белый цвет.
Для каждого запроса выведите ответ на задачу — выведите «Yes», если из ячейки $$$(r_1, c_1)$$$ можно добраться до ячейки $$$(r_2, c_2)$$$, перемещаясь только по белым ячейкам, и «No» иначе.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные ответы.
4 5 20101111110000011110162 1 1 51 4 1 91 4 2 33 5 4 72 2 3 54 7 3 5
Yes No Yes Yes No No
1 2 41131 1 1 81 5 1 41 6 1 7
Yes No Yes
Узор плитки из первого примера приведён на рисунке ниже.
