题目描述

With the development of automation technology, more and more robots have been widely used in various areas. In a package transportation center, there are $q$ robots responsible for the delivery of packages. The package transportation center can be regarded as an $n \ imes m$ grid, where the upper left corner is $(1,1)$ and the lower right corner is $(n,m)$. Considering the actual situation, some (possibly zero) positions in the package transportation center may be unable to pass through (for example, they are blocked by shelves or walls). Let's call those positions unreachable positions.

There are three types of robots listed below:

• robot that can only move downwards, meaning it can only move from $(x,y)$ to $(x+1,y)$.

• robot that can only move rightwards, meaning it can only move from $(x,y)$ to $(x,y+1)$.

• robot that can both move downwards and rightwards.

Robots are demanded to deliver the package from their starting positions to their target positions. For each of the $q$ robots, Toilet-Ares is given its type, starting position, and target position. Toilet-Ares asks you to answer if the robot can complete the package delivery based on the map of the package transportation center.

输入格式

The first line contains two positive integers $n, m(1 \\leq n, m \\leq 500)$, denoting the length and width of the package transportation center.

For the next $n$ lines, each contains a 0-1 string of length $m$, describing the map of the package transportation center. 1 means that the corresponding position is an unreachable positions while 0 means that it isn't.

The $(n+2)$-th line contains a single positive integer $q(1 \\leq q \\leq 5 \\cdot 10^5)$, denoting the number of robots.

For the next $q$ lines, each contains five integers $t,x_1,y_1,x_2,y_2(t \\in \\{1,2,3\\}, 1 \\leq x_1,x_2 \\leq n, 1\\leq y_1,y_2\\leq m)$, denoting each robot's type, starting position, and target position.

It is guaranteed that no starting position or target position is an unreachable positions.

输出格式

For each robot, output a line containing "yes" if the robot can finish its package delivery job, and "no" otherwise.

样例

4 4 
0000 
0000 
0001 
0010 
4 
1 1 1 1 4 
2 2 1 2 4 
3 1 1 3 3 
3 3 3 4 4

no 
yes 
yes 
no

提示

来自:2021牛客暑期多校训练营8

搬运by FrankOu