You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Saturn 星有一座银河系闻名的巨大地下迷宫，吸引了大量游客。由于迷宫过于复杂，经常出现游客迷路的问题，C 君特地制作了一款迷宫导航 APP。

在 C 君的 APP 中，Saturn 星的地下迷宫被描绘成一个 $n\times m$ 的网格图，从上到下第 $x$ 行，从左到右第 $y$ 列的位置用 $(x, y)$ 表示。今天 Saturn 星的地下迷宫迎来了 $q$ 位游客，每位游客都希望探索迷宫中的一段线路，游客们可以在迷宫中每次任选上、下、左、右四个方向之一移动，游客们精力充沛，移动次数没有限制，不过地下迷宫有一些位置摆放了障碍物，游客们不能移动到这些格子上。除此之外，迷宫里还有 $k$ 个有向传送门，当某位游客移动到某个传送门的入口所在格子时，这位游客可以选择传送到传送门的出口格子上。

今天是 C 君第一次测试自己的 APP，C 君希望知道每位游客是否能完成自己的探索路线。

输入格式

第一行有四个整数 $n, m, k, q$ ，表示迷宫的规模，传送门的数量以及游客的数量

然后 $n$ 行每行是一个长度为 $m$ 的字符串，描述迷宫的情况，每个位置可以是 . 或 #，其中 . 表示可以通过，# 表示障碍

然后 $k$ 行，每行4个正整数 $x_1, y_1, x_2, y_2$ ，表示这个传送门的入口是 $\left(x_1, y_1\right)$ ，出口是 $\left(x_2, y_2\right)$

然后 $q$ 行，每行四个正整数 $x_1, y_1, x_2, y_2$ ，表示这位游客的探索起点是 $\left(x_1, y_1\right)$ ，探索终点是 $\left(x_2, y_2\right)$

保证传送门所在位置和游客起点终点不是障碍物

输出格式

输出 $q$ 行，第 $i$ 行表示第 $i$ 位游客能否完成他的探索路线

如果能完成，输出 1，否则输出 0

样例

样例输入1

4 3 2 1
.#.
##.
#..
...
1 1 1 3 
4 1 4 2 
4 1 3 2

样例输出1

1

样例2

b.in
b.out

数据范围与提示

• 对于 $20 \%$ 的数据，满足 $n, m, k, q \leq 20$
• 对于 $60 \%$ 的数据，满足 $n \cdot m \leq 5000, q \leq 2000$
• 对于 $100 \%$ 的数据，满足 $n \cdot m \leq 50000, k \leq 100, q \leq 100000$