题目描述

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

在 C 君的 APP 中，迷宫被描绘成一个 $n\times m$ 的网格。从上到下第 $x$ 行、从左到右第 $y$ 列的位置记为 $(x,y)$。每个格子要么可以通行，要么摆放了障碍物。

今天有 $q$ 位游客前来探索。游客每次可以向上、下、左、右移动到相邻的可通行格子，不能走出网格，也不能进入障碍物格子。游客的移动次数没有限制。

迷宫中还有 $k$ 个有向传送门。每个传送门指定一个入口格子和一个出口格子。当游客位于入口时，可以选择使用这个传送门到达出口，也可以选择不使用它。同一个格子可以连接多个传送门，传送门的入口和出口也可以是同一个格子。

每位游客给定一个起点和一个终点。请判断他能否从起点到达终点。起点与终点可以相同，此时不移动就能完成探索。

输入格式

从文件 map.in 中读入数据。

第一行包含四个整数 $n,m,k,q$，分别表示网格的行数、列数、传送门数量和游客数量。

接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串。字符 . 表示可通行格子，字符 # 表示障碍物。

接下来 $k$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一个从 $(x_1,y_1)$ 通向 $(x_2,y_2)$ 的传送门。

接下来 $q$ 行，每行包含四个整数 $x_1,y_1,x_2,y_2$，表示一位游客的起点为 $(x_1,y_1)$，终点为 $(x_2,y_2)$。

保证所有坐标都在网格内，所有传送门的入口、出口以及游客的起点、终点均为可通行格子。

输出格式

输出到文件 map.out 中。

输出 $q$ 行。第 $i$ 行输出一个整数，若第 $i$ 位游客能够到达终点，输出 1，否则输出 0。

样例 1 输入

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

样例 1 输出

1

样例 1 解释

游客可以沿着 $(4,1)\to(4,2)\to(3,2)$ 行走，不需要使用传送门，因此输出 1。

样例 2

见选手目录下的 map/map2.in 与 map/map2.ans。

该样例满足第 $1\sim4$ 个测试点的限制，$n=m=20,k=q=20$，包含单向传送、反向不可达和起终点相同的情况。

样例 3

见选手目录下的 map/map3.in 与 map/map3.ans。

该样例满足第 $5\sim12$ 个测试点的限制，$n=50,m=100,k=100,q=2000$，包含多个四连通块以及传送门构成的链和支路。

样例 4

见选手目录下的 map/map4.in 与 map/map4.ans。

该样例满足第 $13\sim20$ 个测试点的限制，$n=200,m=250,k=100,q=10^5$，包含长链、支路、重复传送门以及不同类型的询问。

数据范围

对于所有测试数据，保证 $n,m\ge1$，$nm\le50000$，$0\le k\le100$，$1\le q\le10^5$。

测试点	额外限制
$1\sim4$	$n,m,k,q\le20$
$5\sim12$	$nm\le5000,q\le2000$
$13\sim20$	无

共有 $20$ 个测试点，每个测试点独立计 $5$ 分。