C0946 [SDOI2013]escape

髙考又来了，对于不认真读书的来讲真不是个好消息为了小杨能在家里认真读书，他 的亲戚决定驻扎在他的家里监督他学习，有爷爷奶奶、外公外婆、大舅、大嫂、阿姨......

小杨实在是忍无可忍了，这种生活跟监狱有什么区别！为了他亲爱的小红，为了他的 dota,他决定越狱！

假设小杨的家是个 $n \times m$ 的矩阵，左下角坐标为 $(0, 0)$，右上角坐标为（$x_1, y_1$)。小杨有 $n$ 个亲戚，驻扎在矩阵里（位置不同，且不在矩阵的边上）。小杨家里的每个地方都被亲戚监控着，而且只被距离最近的亲戚监控。

也就是说假设小杨所在的位置是 $(3,3)$，亲戚 $A$ 在 $(3,0)$，$A$ 距离小杨距离是 $3$；亲戚 $B$ 在 $(6,7)$，则 $B$ 距离小杨距离是 $5$。距离 $A$ $<$ 距离 $B$，所以 $(3,3)$ 位置由 $A$ 监控。

如果“最近距离”出现同时有几个亲戚，那么那个位置同时被那几个亲戚监控。

给出小杨的坐标（$x_0, y_0$)。因为被发现的人数越少，越狱成功的机会越大，所以小杨需要你设计一条越狱路线到达矩形的边上，且被发现的人数最少。

ps：小杨做的方向是任意的，也就是说路线上的任意位置 $H$ 需要是实数。

保证一开始小杨只被一个亲戚监控着。

样例输入 1

2
4
10 10 5 5
5 6
3 5
7 5
5 3
17
14 12 7 6
7 11
6 9
7 7
1 10
2 20
1 6
2 6
1 1
2 2
5 1
5 2
13 1
12 2
12 7
13 7
12 11
13 11

样例输出 1

1
2