4006번 - 경로 찾기

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

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

현재 점 (X_S,Y_S)에 있다면, 인접한 4점 (즉, (X_S+1,Y_S), (X_S-1,Y_S), (X_S,Y_S+1), (X_S,Y_S-1))중 하나로 날아갈 수 있다.

벌집에는 들어갈 수 없다.

벌집의 변이나 꼭짓점 위에 있을 때만 날아가는 방향을 바꿀 수 있다.

처음에는 상하좌우 네 방향 중 임의의 하나의 방향을 선택하여 출발할 수 있다.

오늘 밤은 Deeficer(TooDee의 복지부 관리)의 딸 생일이므로 Deeficer는 사무실로부터 가능한 빨리 집으로 가고자 한다. Deeficer는 1초에 길이 1의 속도로 날아간다고 가정한다. 위의 규칙을 만족하면서 사무실로부터 가장 빨리 집으로 도착하는데 걸리는 시간(초)를 구하라.

입력의 첫 번째 줄에 테스트 시나리오의 수 T ( 1 ≤ T ≤ 20 ) 가 주어진다. 다음에 T개의 시나리오가 주어진다. 각 시나리오 앞에는 공백 줄이 있다.

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

모든 좌표 값은 10^-9보다 크거나 같고, 10⁹보다 작거나 같으며, 0 ≤ N ≤ 1000이다.

각 시나리오에 대하여, Deeficer가 사무실로부터 집까지 가장 빨리 가는 경로에 의하여 걸리는 시간(초)를 한 줄에 출력한다. 날아가는 규칙을 지키면서 집으로 도달할 수 없으면 "No Path"를 출력한다.