#2304. [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组。 对于每组数据，第一行包含$4$个整数 $x_s, y_s, x_t, y_t$，表示Deeficer 的办公室和 家的坐标分别为$(x_s, y_s)$和$(x_t, y_t)$。第二行包含一个整数n，表示蜂巢的个数。接下 来的n行描述所有的蜂巢，其中第$i$行包含$4$个整数xi1, $y_{i1}, x_{i2}, y_{i2}$，表示第i个 蜂巢两个对角的坐标分别为$(x_{i1}, y_{i1})$和$(x_{i2}, y_{i2})$。 任何两个蜂巢都不会相交，也不会接触（在角上也不会接触）。办公室和家 处在不同的位置。每个蜂巢的面积为正。

输出格式

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

对于100%的测试数据，$1 ≤ n ≤ 1000$，所有坐标都是不超过$10^9$的整数；

样例

样例输入

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

样例输出

9   
No Path

数据范围与提示

数据为国际加国内综合版