골프

JOI-군은 특별한 골프장에서 골프를 연습하는 소년이다. 골프장은 xy좌표가 있는 평면이다. 골프장에는 N개의 장애물이 있다. i번째 장애물은 (1 ≤ i ≤ N) x좌표가 Ai 이상 Bi 이하이고, y좌표가 Ci 이상 Di 이하인 직사각형 영역을 차지한다. 서로 다른 두 장애물은 경계를 포함하여 서로 겹치지 않는다. 이 골프장에서 시작점은 (S , T )이고, 끝점은 (U, V)이다. 두 점은 서로 다르며, 어떤 장애물이나 그 경계에도 포함되지 않는다. 처음에 골프공은 시작점에 놓여 있다. JOI-군은 골프공을 쳐서 평면의 어느 한 좌표축과 평행한 네 방향 중 어느 방향으로든 임의의 거리만큼 움직일 수 있다. 단, 공의 궤적은 어떤 장애물의 내부에도 닿아서는 안 된다. 공은 장애물의 경계 위를 지나갈 수 있다. 공은 장애물의 경계 위에서 멈출 수 있다. 그런 다음 장애물이 없는 방향으로 공을 쳐서 이동 방향을 바꿀 수 있다. JOI-군은 골프장을 끝내는 데 필요한 최소 타수를 알고 싶어 한다. 당신은 JOI-군의 골프 친구이므로, 그는 당신에게 이를 계산해 달라고 부탁한다. 공을 시작점에서 끝점까지 옮기는 데 필요한 최소 타수는 얼마인가?

골프장의 정보가 주어질 때, 공을 시작점에서 끝점까지 옮기는 데 필요한 최소 타수를 계산하는 프로그램을 작성하라.

제약 조건

모든 입력 데이터는 다음 조건을 만족한다.

• 1 ≤ S ≤ 1 000 000 000.

• 1 ≤ T ≤ 1 000 000 000.

• 1 ≤ U ≤ 1 000 000 000.

• 1 ≤ V ≤ 1 000 000 000.

• 1 ≤ N ≤ 100 000.

• 1 ≤ Ai < Bi ≤ 1 000 000 000 (1 ≤ i ≤ N).

• 1 ≤ Ci < Di ≤ 1 000 000 000 (1 ≤ i ≤ N).

• (S , T ) , (U, V).

• 서로 다른 두 장애물은 경계를 포함하여 서로 겹치지 않는다.

• 시작점과 끝점은 어떤 장애물이나 그 경계에도 포함되지 않는다.

부분 과제

부분 과제는 3개이다. 각 부분 과제의 점수와 추가 제약 조건은 다음과 같다.

부분 과제 1 [10점] • S ≤ 1 000.

• T ≤ 1 000.

• U ≤ 1 000.

• V ≤ 1 000.

• N ≤ 1 000.

• Bi ≤ 1 000 (1 ≤ i ≤ N).

• Di ≤ 1 000 (1 ≤ i ≤ N).

부분 과제 2 [20점] • N ≤ 1 000.

부분 과제 3 [70점] 추가 제약 조건은 없다.

표준 입력에서 다음 데이터를 읽는다. • 입력의 첫째 줄에는 공백으로 구분된 네 정수 S , T, U, V가 주어진다. 이는 시작점의 x좌표가 S , 시작점의 y좌표가 T , 끝점의 x좌표가 U, 끝점의 y좌표가 V임을 뜻한다.

• 입력의 둘째 줄에는 장애물의 수를 나타내는 정수 N이 주어진다.

• 이어지는 N개 줄 중 i번째 줄에는 (1 ≤ i ≤ N) 공백으로 구분된 네 정수 Ai , Bi , Ci , Di 가 주어진다. 이는 i번째 장애물이 x좌표가 Ai 이상 Bi 이하이고, y좌표가 Ci 이상 Di 이하인 직사각형 영역을 차지한다는 뜻이다.

표준 출력에 한 줄을 출력한다. 출력에는 골프공을 시작점에서 끝점까지 옮기는 데 필요한 최소 타수가 주어진다.