Comet OJ

C0466 [APIO2011-B]寻路

内存限制：256 MB 时间限制：2000 ms

题目描述

TooDee 是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里生活着很多可爱的 Dee。Dee 是像蜜蜂一样的小动物，它们只在二维活动，而且它们非常的文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的，它们是矩形的且它们的边平行于 TooDee 的地理坐标系，就是说矩形的边或者是东西走向，或者是南北走向。

因为 Dees 是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些平行于坐标轴的线段组成，线段只会在经纬度都是整数的点相交。Dee 在 TooDee 飞行时必须遵守以下规则（请记住 TooDee 中所有点的经纬度都是整数）：

  • 如果当前在点 $(X_S,Y_S)$，则下步只能飞到四个邻点 $(X_S,Y_S–1)$, $(X_S,Y_S+ 1)$,$(X_S–1,Y_S)$,$(X_S+1,Y_S)$；

  • 不可以进入蜂巢；

  • 只能在蜂巢的角或者边上改变飞行方向；

  • 开始的时候可以向任何方向飞；

今晚是公共财政大臣 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$ 个整数 $x_{i1},y_{i1},x_{i2},y_{i2}$，表示第 $i$ 个蜂巢两个对角的坐标分别为 $(x_{i1},y_{i1})$ 和 $(x_{i2},y_{i2})$。

任何两个蜂巢都不会相交，也不会接触（在角上也不会接触）。办公室和家处在不同的位置。每个蜂巢的面积为正。

输出

对于每一组数据，输出一个整数，表示 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≤10$，所有的坐标都是小于 100 的非负整数；
对于60%的测试数据，$n≤100$，所有坐标的绝对值都小于 1000；
对于100%的测试数据，$1≤n≤1000$，所有坐标都是不超过 $10^9$ 的整数；