|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||1024 MB||9||8||7||87.500%|
JOI-kun is a boy practicing golf in a special golf course.
The course is a plane with xy-coordinates. There are N obstacles on the course. The i-th obstacle (1 ≤ i ≤ N) occupies the rectangular region whose x-coordinates are greater than or equal to Ai and less than or equal to Bi, and y-coordinates are greater than or equal to Ci and less than or equal to Di. Two obstacles (including their boundaries) do not intersect with each other.
In this course, the start point is (S, T), and the end point is (U, V). These points are different, and not contained in any obstacles and their boundaries. In the beginning, the golf ball is placed at the start point.
JOI-kun can hit the golf ball, and move it for any distance toward any of four directions parallel to one of the coordinates of the plane. But, the track of the ball should not touch the interior of any obstacles. The ball can pass through the boundaries of the obstacles. It can stop on the boundary of an obstacle. Then, it can change the direction to move by hitting it toward the direction in which there is no obstacle.
JOI-kun wants to know the minimum number of hits needed to finish the course. Because you are JOI-kun’s golf friend, he asks you to calculate it.
What is the minimum number of hits needed to move the ball from the start point to the end point?
Given the information of the golf course, write a program which calculates the minimum number of hits needed to move the ball from the start point to the end point.
Read the following data from the standard input.
Write one line to the standard output. The output contains the minimum number of hits needed to move the golf ball from the start point to the end point.
All input data satisfy the following conditions.
There are no additional constraints.
3 5 8 6 1 5 6 2 8
In this sample input, for example, JOI-kun can move the golf ball as (3,5) → (3,2) → (8,2) → (8,6) from the start point to the end point; he needs three hits for this. Since it is impossible to move the ball by less than three hits, output 3.
1 1 1 10 3 5 6 2 8 1 2 2 3 8 10 3 5
In this sample input, JOI-kun needs one hit to move the golf ball from the start point to the end point.
20 68 85 74 5 30 70 14 100 5 24 15 67 75 86 75 79 75 90 19 62 93 98 26 58