TooDee는 직교좌표 시스템인 2차원 그리드-형태의 지역 이름이다. 이 지역에는 귀여운 Dee들이 살고 있다. Dee들은 벌처럼 생긴 작은 2-차원 모양의 생동물로서 아주 영리하다. TooDee에는 벌집들이 있는데, 이 벌집은 보통의 벌집과는 달리 직사각형 형태로 벌집의 각 변이 TooDee의 직교좌표의 축에 평행하다.

Dee들은 매우 특별히 진화된 동물이므로 일정한 경로로 날아간다. 이 경로는 직교좌표 축 과 평행한 (수형 혹은 수직의) 선분들로 구성되며. 이 선분들의 양 끝 점의 좌표값은 모두 정수라 가정한다. 직교좌표 시스템 표기를 사용할 때, TooDee 지역에서 모든 Dee들이 날아 가는 규칙은 다음과 같다. (TooDee 지역에서 언급되는 모든 점의 위치 값은 정수이다.)

• 현재 점 (Xs,Ys)에 있다면, 인접한 4 점 즉,(Xs+1,Ys),(Xs-1,Ys),(Xs,Ys+1),(Xs,Ys-1) 중 하나로 날아갈 수 있다.
• 벌집에는 들어갈 수 없다.
• 벌집의 변이나 꼭지점 위에 있을 때만 날아가는 방향을 바꿀 수 있다.
• 처음에는 상하좌우 네 방향 중 임의의 하나의 방향을 선택하여 출발할 수 있다.

입력

다음에 T 개의 시나리오가 주어진다. 각 시나리오 앞에는 공백 줄이 있다.

각 시나리오의

• 첫 번째 줄에는 Deeficer의 사무실 위치와 집의 위치를 포함한다. 이들 각 위치는 X 좌표 값과 Y 좌표 값의 두 정수로 주어진다.
• 각 시나리오의 두 번째 줄에 벌집 의 수 N 이 주어진다. 다음의 N냅각 줄에 벌집 하나의 정보가 주어진다. 이 정보는 벌집 직사각형의 대각선으로 마주보는 두 꼭지점의 좌표들로 주어진다. 모든 두 벌집은 서로 겹치지 않으며, 두 벌집의 변이 붙어 있지도 않고, 두 벌집의 꼭지점들이 만나지도 않는다. 사무실과 집의 위치는 서로 다르고, 벌집의 면적은 1 이상이다.

모든 테스트 케이스에서, 모든 좌표 값은 -10⁹보다 같거나 크고 10⁹보다 같거나 작으 며, 0 ≤ N ≤ 1000 이다.

출력

날아가는 규칙을 지키면서 집으로 도달할 수 없으면 “No Path"를 출력한다.

입출력 예

입력

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

출처:apio 2011 년 문제 2 번