John Doe 有一个字段,它是一个大小为 n × m 的矩形表。我们假设字段行从上到下编号为 1 到 n,字段列从左到右编号为 1 到 m。那么第 x 行和第 y 列交叉处的字段单元格的坐标为 (x; y)。
我们知道约翰视野中的一些单元格被漆成白色,一些单元格被漆成黑色。此外,约翰还有一只乌龟,它可以沿着视野中的白细胞移动。乌龟可以从坐标为 (x; y) 的白色单元格进入 (x + 1; y) 或 (x; y + 1) 单元格,如果相应的单元格被涂成白色。换句话说,海龟只能沿着区域的白细胞向右或向下移动。乌龟不能走出场地范围。
另外,John 有 q 个查询,每个查询都由四个数字 x1, y1, x2, y2 表征(x1 ≤ x2, y1 ≤ y2)。对于每个查询,约翰想知道乌龟是否可以从坐标为 (x1; y1) 的点出发,并到达坐标为 (x2; y2) 的点,仅沿着田野的白色方块移动。
输入
第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 500) — 字段大小。
接下来的 n 行中的每一行都包含 m 个字符“#”和“.”:如果单元格 (i; j) 被涂成黑色,则第 i 行的第 j 个字符等于“#”;如果单元格 (i; j) 被涂成白色,则第 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 查询,如果存在满足要求的从单元格 (x1; y1) 到单元格 (x2; y2) 的路径,则在单行上打印“是”,否则打印“否”。按顺序打印查询的答案,其中查询在输入中给出。
示例
输入 #1
3 3 ... .## .#. 5 1 1 3 3 1 1 1 3 1 1 3 1 1 1 1 2 1 1 2 1
输出 #1
No Yes Yes Yes Yes
输入 #2
5 5 ..... .###. ..... .###. ..... 5 1 1 5 5 1 1 1 5 1 1 3 4 2 1 2 5 1 1 2 5
输出 #2
Yes Yes Yes No Yes