[APIO2011]寻路

题目描述

TooDee 是一块二维格子状的土地(就像著名的笛卡尔坐标系那样),在这里生活着很多可爱的 Dee。Dee 是像蜜蜂一样的小动物,它们只在二维活动,而且他们非常的 文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的,他们是矩形的且它们的边平行于 TooDee 的地理坐标系,就是说矩形的边或者是东西走向, 或者是南北走向。 因为 Dees 是很高级的生物,他们有很多固定的飞行轨道,这些轨道由一些平行于坐标轴的线段组成,线段只会在经纬度都是整数的点相交。Dee 在 TooDee 飞行时必须遵守以下规则(请记住 TooDee 中所有点的经纬度都是整数): 1. 如果当前在点 $(X, Y)$,则下一步只能飞到四个邻点 $(X, Y - 1), (X, Y + 1), (X - 1, Y), (X + 1, Y)$; 2. 不可以进入蜂巢; 3. 只能在蜂巢的角上或者边上改变飞行方向; 4. 开始的时候可以向任何方向飞; 今晚是公共财政大臣 Deeficer 的女儿的生日,她想尽早回家,请帮她找到最快的回家路径。假设她每秒可以飞行一个单位的距离。

输入输出格式

输入格式


每个测试点包含多组数据。 输入的第一行包含一个整数 $T$,表示测试数据的组数。接下来依次描述这 $T$ 组数据,相邻的两组之间使用一个空行分隔,测试数据不多于 $20$ 组。 对 于每组数据,第一行包含四个整数 $x_s,y_s,x_t,y_t$,表示 Deeficer 的办公室和家的坐标分别是 $(x_s, y_s)$ 和 $(x_t, y_t)$。第二行包含一个整数 $n$,表示蜂巢的个数。接下来的 $n$ 行描述所有的蜂巢,其中第 $i$ 行包含四个整数 $x_{i_1}, y_{i_1}, x_{i_2}, y_{i_2}$,表示第 $i$ 个蜂巢两个对角的坐标分别为 $(x_{i_1}, y_{i_1})$ 和 $(x_{i_2}, y_{i_2})$。 任何两个蜂巢不会相交,也不会接触(在角上也不会接触)。办公室和家处在不同的位置。每个蜂巢的面积为正。

输出格式


对于每一组数据,输出一个整数,表示 Deeficer 最快回家的时间(单位为秒),如果她无法按规则回家,则输出 `No Path`。

输入输出样例

输入样例 #1

2
1 7 7 8
2
2 5 3 8
4 10 6 7
2 1 5 4
1
3 1 4 3

输出样例 #1

9
No Path

说明

对于 $20\%$ 的测试数据,$n\leq 10$,所有的坐标都是小于 $100$ 的非负整数; 对于 $60\%$ 的测试数据,$n\leq 100$,所有坐标的绝对值都小于 $10^3$; 对于 $100\%$ 的测试数据,$0\leq n\leq 10^3$,所有坐标的绝对值都是不超过 $10^9$ 的整数。