描述

尼莫是一个顽皮的小男孩。一天，他独自一人进入了深海。不幸的是，他迷路了，找不到回家的路。于是，他向他的父亲马林发送了一个信号，请求帮助。

马林查看地图后发现，海洋就像一个迷宫，有墙壁和门。所有的墙壁都平行于X轴或Y轴。假设墙壁的厚度为零。

所有的门都开在墙壁上，长度为1。马林不能穿过没有门的墙壁。因为穿过门是危险的（门附近可能有一些有毒的水母），马林希望尽可能少地穿过门以找到尼莫。

图1展示了一个迷宫的例子以及马林找到尼莫的路径。

我们假设马林的初始位置在(0, 0)。给定尼莫的位置以及墙壁和门的配置，请编写一个程序来计算马林到达尼莫所需的最少门的数量。

输入

输入包含多个测试用例。每个测试用例以两个非负整数 $M$ 和 $N$ 开始。$M$ 表示迷宫中的墙壁数量，$N$ 表示门的数量。

接下来的 $M$ 行，每行包含四个整数，描述一面墙壁，格式如下：

x y d t

(x, y) 表示墙壁的左下角点，$d$ 是墙壁的方向——0表示平行于X轴，1表示平行于Y轴，$t$ 是墙壁的长度。

任何墙壁的两个端点的坐标将在 [1, 199] 范围内。

接下来的 $N$ 行描述门：

x y d

x, y, d 的含义与墙壁相同。由于门的长度固定为1，因此省略了 $t$。

每个测试用例的最后一行包含两个正浮点数：

f1 f2

(f1, f2) 给出了尼莫的位置。它不会位于任何墙壁或门内。

一个测试用例 $M = -1$ 和 $N = -1$ 表示输入结束，不应被处理。

输出

对于每个测试用例，在单独的一行中，请输出马林营救他的儿子所需的最少门的数量。如果他无法到达尼莫，输出 -1。

输入数据 1

8 9  
1 1 1 3  
2 1 1 3  
3 1 1 3  
4 1 1 3  
1 1 0 3  
1 2 0 3  
1 3 0 3  
1 4 0 3  
2 1 1  
2 2 1  
2 3 1  
3 1 1  
3 2 1  
3 3 1  
1 2 0  
3 3 0  
4 3 1  
1.5 1.5  
4 0  
1 1 0 1  
1 1 1 1  
2 1 1 1  
1 2 0 1  
1.5 1.7  
-1 -1

输出数据 1

5  
-1

来源

北京2004